project euler #10, java, correct for small numbers

Question

*disclaimer, when I say "I have verified this is the correct result", please interpret this as I have checked my solution against the answer according to WolframAlpha, which I consider to be pretty darn accurate.

*goal, to find the sum of all the prime numbers less than or equal to 2,000,000 (two million)

*issue, my code will output the correct result whenever my range of tested values is approximately less than or equal to

I do not output correct result once test input becomes larger than approximately 1,300,000; my output will be off...

test input: ----199,999 test output: ---1,709,600,813 correct result: 1,709,600,813

test input: ----799,999 test output: ---24,465,663,438 correct result: 24,465,663,438

test input: ----1,249,999 test output: ---57,759,511,224 correct result: 57,759,511,224

test input: ----1,499,999 test output:--- 82,075,943,263 correct result: 82,074,443,256

test input: ----1,999,999 test output:--- 142,915,828,925 correct result: 142,913,828,925

test input: ----49,999,999 test output:--- 72,619,598,630,294 correct result: 72,619,548,630,277

*my code, what's going on, why does it work for smaller inputs? I even used long, rather than int...

long n = 3;
long i = 2;
long prime = 0;
long sum = 0;
while (n <= 1999999) {
  while (i <= Math.sqrt(n)) {    // since a number can only be divisible by all
                            // numbers
                            // less than or equal to its square roots, we only
                            // check from i up through n's square root!
    if (n % i != 0) {       // saves computation time
      i += 2;               // if there's a remainder, increment i and check again
    } else {
      i = 3;                // i doesn't need to go back to 2, because n+=2 means we'll
                            // only ever be checking odd numbers
      n += 2;               // makes it so we only check odd numbers
    }
  }                         // if there's not a remainder before i = n (meaning all numbers from 0
                            // to n were relatively prime) then move on
  prime = n;                // set the current prime to what that number n was
  sum = sum + prime;
  i = 3;                    // re-initialize i to 3
  n += 2;                   // increment n by 2 so that we can check the next odd number

}
System.out.println(sum+2); // adding 2 because we skip it at beginning

help please :)

Answer 1

The problem is that you don't properly check whether the latest prime to be added to the sum is less than the limit. You have two nested loops, but you only check the limit on the outer loop:

while (n <= 1999999) {

But you don't check in the inner loop:

 while (i <= Math.sqrt(n)) {

Yet you repeatedly advance to the next candidate prime (n += 2;) inside that loop. This allows the candidate prime to exceed the limit, since the limit is only checked for the very first candidate prime in each iteration of the outer loop and not for any subsequent candidate primes visited by the inner loop.

To take an example, in the case with the limit value of 1,999,999, this lets in the next prime after 1,999,999, which is 2,000,003. You'll note that the correct value, 142,913,828,922, is exactly 2,000,003 less than your result of 142,915,828,925.

A simpler structure

Here's one way the code could be structured, using a label and continue with that label to simplify structure:

public static final long primeSum(final long maximum) {
    if (maximum < 2L) return 0L;
    long sum = 2L;

    // Put a label here so that we can skip to the next outer loop iteration.
    outerloop:
    for (long possPrime = 3L; possPrime <= maximum; possPrime += 2L) {
        for (long possDivisor = 3L; possDivisor*possDivisor <= possPrime; possDivisor += 2L) {
            // If we find a divisor, continue with the next outer loop iteration.
            if (possPrime % possDivisor == 0L) continue outerloop;
        }
        // This possible prime passed all tests, so it's an actual prime.
        sum += possPrime;
    }

    return sum;
}