Return to Answer

Some comments on the code:

Don't write a big main, this makes the code unusable for anything but the current demo. Whenever main gets more than a few lines, extract a method. Btw., Java loves short methods and optimizes them way better than long ones.

Move constants out of methods. Actually, int maxNumber = 1000; should be an argument. Then a comment like

// maxNumber must be an even number

is obviously not enough. You need a Javadoc. And then don't be afraid of

if (maxNumber % 2 != 0) {
    throw new IllegalArgumentException("maxNumber must be an even");
}

as trying to process wrong input is waste of time at best.

Try to separate the output from the computation, even for small programs. This is sometimes more work, but you get a reusable result ad it helps you write cleaner code.

If you're interested in optimization, be assured that it's hard. And also fun. In Java it's especially complicated and usually you need some benchmarking framework (they're free).

The code is multiplying possibly big numbers, but I can't see any guarantee that they don't overflow. When I increased the limit to 1.3e9, problems came. That's not that bad as it's close enough to the maximum possible input (so adding a check would do).

The code is badly missing a test. The idea is good (though I still don't understand it fully), but it may produce wrong results. Testing each prime below Integer.MAX_VALUE via BigInteger.isProbablePrime should be doable.

Some code pieces should be improved, e.g.

secondPrime += 2;
while (!isPrime[secondPrime]) {
    secondPrime += 2;
}

is a do-while loop. This piece

while (true) {
    if (square <= maxNumber) {
        isPrime[square] = false;
        square += (prime * prime * 2);
    }
    else {
        secondPrime += 2;
        break;
    }
}

is nothing but

while (square <= maxNumber) {
    isPrime[square] = false;
    square += (prime * prime * 2);
}
secondPrime += 2;

After a few similar changes and some debugging, I finally understood what it's all about.

It's pretty fast and clever. The speed comes from testing only

• products p*q with both multiplicands being primes and p<q and
• multiples of p**2 for a prime p

Finding this out from the code alone is a like the twelve labours of Hercules. No offense, this happens quite often with optimized code. That's what CR is for.

Some comments on the code:

Don't write a big main, this makes the code unusable for anything but the current demo. Whenever main gets more than a few lines, extract a method. Btw., Java loves short methods and optimizes them way better than long ones.

Move constants out of methods. Actually, int maxNumber = 1000; should be an argument. Then a comment like

// maxNumber must be an even number

is obviously not enough. You need a Javadoc. And then don't be afraid of

if (maxNumber % 2 != 0) {
    throw new IllegalArgumentException("maxNumber must be an even");
}

as trying to process wrong input is waste of time at best.

Try to separate the output from the computation, even for small programs. This is sometimes more work, but you get a reusable result ad it helps you write cleaner code.

If you're interested in optimization, be assured that it's hard. And also fun. In Java it's especially complicated and usually you need some benchmarking framework (they're free).

The code is multiplying possibly big numbers, but I can't see any guarantee that they don't overflow. When I increased the limit to 1.3e9, problems came. That's not that bad as it's close enough to the maximum possible input (so adding a check would do).

The code is badly missing a test. The idea is good (though I still don't understand it fully), but it may produce wrong results. Testing each prime below Integer.MAX_VALUE via BigInteger.isProbablePrime should be doable.

Some code pieces should be improved, e.g.

secondPrime += 2;
while (!isPrime[secondPrime]) {
    secondPrime += 2;
}

is a do-while loop. This piece

while (true) {
    if (square <= maxNumber) {
        isPrime[square] = false;
        square += (prime * prime * 2);
    }
    else {
        secondPrime += 2;
        break;
    }
}

is nothing but

while (square <= maxNumber) {
    isPrime[square] = false;
    square += (prime * prime * 2);
}
secondPrime += 2;

After a few similar changes and some debugging, I finally understood what it's all about.

It's pretty fast and clever. The speed comes from testing only

• products p*q with p being a prime, isPrime[q] being true¹, and p<q
• multiples of p**2 for a prime p

Finding this out from the code alone is a like the twelve labours of Hercules. No offense, this happens quite often with optimized code. That's what CR is for.

¹ Because of q being a either prime or not yet detected composite number.

Some comments on the code:

Don't write a big main, this makes the code unusable for anything but the current demo. Whenever main gets more than a few lines, extract a method. Btw., Java loves short methods and optimizes them way better than long ones.

Move constants out of methods. Actually, int maxNumber = 1000; should be an argument. Then a comment like

// maxNumber must be an even number

is obviously not enough. You need a Javadoc. And then don't be afraid of

if (maxNumber % 2 != 0) {
    throw new IllegalArgumentException("maxNumber must be an even");
}

as trying to process wrong input is waste of time at best.

Try to separate the output from the computation, even for small programs. This is sometimes more work, but you get a reusable result ad it helps you write cleaner code.

If you're interested in optimization, be assured that it's hard. And also fun. In Java it's especially complicated and usually you need some benchmarking framework (they're free).

The code is multiplying possibly big numbers, but I can't see any guarantee that they don't overflow. I've tried to do something similar and got quite a few.

The code is badly missing a test. The idea is good (though I still don't understand it fully), but it may produce wrong results. Testing each prime below Integer.MAX_VALUE via BigInteger.isProbablePrime should be doable.

(to be continued soon)

Some comments on the code:

Don't write a big main, this makes the code unusable for anything but the current demo. Whenever main gets more than a few lines, extract a method. Btw., Java loves short methods and optimizes them way better than long ones.

Move constants out of methods. Actually, int maxNumber = 1000; should be an argument. Then a comment like

// maxNumber must be an even number

is obviously not enough. You need a Javadoc. And then don't be afraid of

if (maxNumber % 2 != 0) {
    throw new IllegalArgumentException("maxNumber must be an even");
}

as trying to process wrong input is waste of time at best.

Try to separate the output from the computation, even for small programs. This is sometimes more work, but you get a reusable result ad it helps you write cleaner code.

If you're interested in optimization, be assured that it's hard. And also fun. In Java it's especially complicated and usually you need some benchmarking framework (they're free).

The code is multiplying possibly big numbers, but I can't see any guarantee that they don't overflow. When I increased the limit to 1.3e9, problems came. That's not that bad as it's close enough to the maximum possible input (so adding a check would do).

The code is badly missing a test. The idea is good (though I still don't understand it fully), but it may produce wrong results. Testing each prime below Integer.MAX_VALUE via BigInteger.isProbablePrime should be doable.

Some code pieces should be improved, e.g.

secondPrime += 2;
while (!isPrime[secondPrime]) {
    secondPrime += 2;
}

is a do-while loop. This piece

while (true) {
    if (square <= maxNumber) {
        isPrime[square] = false;
        square += (prime * prime * 2);
    }
    else {
        secondPrime += 2;
        break;
    }
}

is nothing but

while (square <= maxNumber) {
    isPrime[square] = false;
    square += (prime * prime * 2);
}
secondPrime += 2;

After a few similar changes and some debugging, I finally understood what it's all about.

It's pretty fast and clever. The speed comes from testing only

• products p*q with both multiplicands being primes and p<q and
• multiples of p**2 for a prime p

Finding this out from the code alone is a like the twelve labours of Hercules. No offense, this happens quite often with optimized code. That's what CR is for.

Some comments on the code:

Don't write a big main, this makes the code unusable for anything but the current demo. Whenever main gets more than a few lines, extract a method. Btw., Java loves short methods and optimizes them way better than long ones.

Move constants out of methods. Actually, int maxNumber = 1000; should be an argument. Then a comment like

// maxNumber must be an even number

is obviously not enough. You need a Javadoc. And then don't be afraid of

if (maxNumber % 2 != 0) {
    throw new IllegalArgumentException("maxNumber must be an even");
}

as trying to process wrong input is waste of time at best.

Try to separate the output from the computation, even for small programs. This is sometimes more work, but you get a reusable result ad it helps you write cleaner code.

If you're interested in optimization, be assured that it's hard. And also fun. In Java it's especially complicated and usually you need some benchmarking framework (they're free).

(to be continued soon)

Some comments on the code:

Don't write a big main, this makes the code unusable for anything but the current demo. Whenever main gets more than a few lines, extract a method. Btw., Java loves short methods and optimizes them way better than long ones.

Move constants out of methods. Actually, int maxNumber = 1000; should be an argument. Then a comment like

// maxNumber must be an even number

is obviously not enough. You need a Javadoc. And then don't be afraid of

if (maxNumber % 2 != 0) {
    throw new IllegalArgumentException("maxNumber must be an even");
}

as trying to process wrong input is waste of time at best.

Try to separate the output from the computation, even for small programs. This is sometimes more work, but you get a reusable result ad it helps you write cleaner code.

If you're interested in optimization, be assured that it's hard. And also fun. In Java it's especially complicated and usually you need some benchmarking framework (they're free).

The code is multiplying possibly big numbers, but I can't see any guarantee that they don't overflow. I've tried to do something similar and got quite a few.

The code is badly missing a test. The idea is good (though I still don't understand it fully), but it may produce wrong results. Testing each prime below Integer.MAX_VALUE via BigInteger.isProbablePrime should be doable.

(to be continued soon)