Project Euler, Problem 10 java solution not working

Question

Hi, I'm trying to find the sum of the prime numbers < 2,000,000. This is my solution in java but I can't seem get the correct answer. Please give some input on what could be wrong and general advice on the code is appreciated.

Printing 'sum' gives: 1308111344, which is incorrect.

edit: Thanks for all the help. Changed int to long and < to <= and it worked flawlessly, except for being an inefficient way of finding prime numbers :)

/*
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
*/
class Helper{
 public void run(){
  Integer sum = 0;
  for(int i = 2; i < 2000000; i++){
   if(isPrime(i))
    sum += i;   
  }
  System.out.println(sum);
 }

 private boolean isPrime(int nr){
  if(nr == 2)
   return true;
  else if(nr == 1)
   return false;
  if(nr % 2 == 0)
   return false;

  for(int i = 3; i < Math.sqrt(nr); i += 2){
   if(nr % i == 0)
    return false;
  }  
  return true;  
 }
}   
class Problem{
 public static void main(String[] args){
  Helper p = new Helper();
p.run();
}
}

Answer 1

The result will be too large to fit into an integer, so you are getting an overflow. Try using a BigInteger or a long instead. In this case a long is enough.

Answer 2

You're treating as prime those numbers that are only divisible by their square root (like 25). Instead of i < Math.sqrt(nr) try i <= Math.sqrt(nr).

That's a really inefficient way to find primes, incidentally.

Answer 3

Your isPrime doesn't work for squares. isPrime(9) returns true.

Answer 4

As already stated errors were two:

• you used an int that is not big enough to hold that sum.. you should have used a long
• you used < instead that <=, and it was a wrong guard for the cycle

Apart from that what you are doing is really inefficient, without going too deep inside this class of algorithms (like Miller-Rabin test) I would suggest you to take a look to the Sieve of Eratosthenes.. a really old approach that teaches how to treat a complex problem in a simple manner to improve elegance and efficiency with a trade-off of memory.

It's really cleaver: it keeps track of a boolean value for every prime up to your 2 millions that asserts if that number is prime or not. Then starting from the first prime it excludes all the successive numbers that are obtained by multiplying the prime it is analyzing for another number. Of couse more it goes and less numbers it will have to check (since it already excluded them)

Code is fair simple (just wrote it on the fly, didn't check it):

    boolean[] numbers = new boolean[2000000];
    long sum = 0;

    for (int i = 0; i < numbers.length; ++i)
        numbers[i] = true;

    for (int i = 2; i < numbers.length; ++i)
        if (!numbers[i])
            continue;
        else {
            int j = i + i;
            while (j < 2000000) {                   
                numbers[j] = false;
                j += i;
            }           
        }

    for (int i = 2; i < 2000000; ++i)
        sum += numbers[i] ? i : 0;

    System.out.println(sum);

Of course this approach is still unsuitable for high numbers (because it has to find all the previous primes anyway and because of memory) but it's a good example for starters to think about problems..