Skip to main content
alternative suggestion to prevent overrun of isPrime array
Source Link
David K
  • 1.2k
  • 8
  • 8
                    while (secondPrime <<= maxNumber && !isPrime[secondPrime]) {

but it would guarantee no running ofoff the end of the array, and it would take far less development time to achieve that guarantee. Alternatively, you could allocate an additional element in the isPrime array that would act as a "guard byte": that is, you allocate space for isPrime[maxNumber + 1] and set isPrime[maxNumber + 1] = true, and rely on your other logic to ensure that you will never set isPrime[maxNumber + 1] = false (and also never actually use maxNumber + 1 as a prime number).

                    while (secondPrime < maxNumber && !isPrime[secondPrime]) {

but it would guarantee no running of the end of the array, and it would take far less development time to achieve that guarantee.

                    while (secondPrime <= maxNumber && !isPrime[secondPrime]) {

but it would guarantee no running off the end of the array, and it would take far less development time to achieve that guarantee. Alternatively, you could allocate an additional element in the isPrime array that would act as a "guard byte": that is, you allocate space for isPrime[maxNumber + 1] and set isPrime[maxNumber + 1] = true, and rely on your other logic to ensure that you will never set isPrime[maxNumber + 1] = false (and also never actually use maxNumber + 1 as a prime number).

Source Link
David K
  • 1.2k
  • 8
  • 8

The revisions you've already made (variable names, and especially consistent indentation of {, }, and the things between them, helps a lot.

It's still better to organize the code in several functions instead of one main() function. Among other things, this helps reduce the required indentation of some of the code. But mainly it makes functionality a lot easier to see. At a minimum, the code that does the sieving and the code that prints the results should each be in independent functions.

Consider this code fragment:

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

This appears to serve the function of changing secondPrime to the next larger prime. You could put something like this in the body of a function which you would then call like this:

                    secondPrime = getPrimeAfter(secondPrime);

In fact, maybe you could use this to write

            for (int secondPrime = prime, square = prime * prime; 
                 secondPrime * prime <= maxNumber;
                 secondPrime = getPrimeAfter(secondPrime)) {

which would make the for statement a bit better organized. (I am always uncomfortable when the "advance to the next iteration value" code is not between the second ; and the ) of the for loop control structure. The only question about this is that in the other main branch of logic within that same for loop, you wrote

                            secondPrime += 2;

... that is, in this case you don't increase secondPrime to the next prime, but rather just to the next odd number. The fact that you chose secondPrime as a name of this variable, however, suggests that you didn't actually mean to stop at the next odd number when that number isn't prime, so maybe you do really want to increase secondPrime in the same way on every iteration of the for (int secondPrime loop. Defining and using a function such as getPrimeAfter(int) will help avoid this error (if it is an error) and make it clearer what is actually supposed to happen.

It looks like the variable named square is actually multipleOfSquare; that is, it takes on the values primeprime, 3primeprime, 5prime*prime, and so forth.

Consider this line:

                if (secondPrime * prime == square && square < maxNumber / 2) {

If secondPrime is, in fact, a prime, then this condition can be true only on the first iteration, when secondPrime == prime. That would suggest that it might be better to execute the code of this if branch just once before the loop and only do the else code during the loop. (On the other hand, since the code as it stands at this moment does not appear to guarantee that secondPrime is prime, it's hard to determine exactly what would happen if you reorganized that loop as I just suggested.)

These three comments have me a bit confused:

                // if the product of 'prime' and 'secondPrime' equals
                // 'square'

                    // searches for all multiples of square that may exist in
                    // array

                // if 'prime' and 'secondPrime' are not equal to square
                // then search for all multiples of 'prime' by 'secondPrime'

The first comment is pretty useless, since it just says exactly what the first part of the if condition below says. In the second comment, we know that secondPrime * prime == square, so actually this is searching for all multiples of secondPrime*prime. But that's just what the third comment says. So do the if and else branches of if (secondPrime * prime == square (the branch with the second comment and the branch with the third comment) actually do anything different from each other? Do you really need two branches? If so, that's what you should explain in the comments.

You might be able to save some computation here:

    for (int prime = 5; prime * prime <= maxNumber; prime += 2) {
        // the if-statement below skips the testing of all non-prime numbers
        if (isPrime[prime]) {

If you compute the square root of maxNumber just once at the very start of the sieve, you could write prime <= maxSquareRoot instead of prime * prime <= maxNumber, and save a multiplication on every iteration. Another question is whether you could use prime = getPrimeAfter(prime) instead of prime += 2. Before doing that, you should show that getPrimeAfter(prime) will always terminate before its internal iterator runs off the end of the isPrime array. But come to think of it, you really should also establish that fact in the place where you write

                    while (!isPrime[secondPrime]) {

deep within the bowels of your sieve. On the other hand, it might slow your code down a tiny bit if you change that line to

                    while (secondPrime < maxNumber && !isPrime[secondPrime]) {

but it would guarantee no running of the end of the array, and it would take far less development time to achieve that guarantee.