Find the sum of all the primes below two million.My program doesn't work for very big numbers

your answer is 142913828922 but how?

I just changed your algorithm a little bit:

public static void main(String[] args) {

    BigInteger sum = new BigInteger("2");
    boolean isPrime = true;
    for (int i=3; i<2000000; i++) {
    double aa = Math.sqrt((double)i);
        for (int j=2; j<=aa; j++){
            if (i % j == 0){ 
                isPrime = false;
                break;
            }
        }
        if(isPrime){
            sum = sum.add(BigInteger.valueOf(i));
        }
        isPrime = true;
    }
    System.out.println("Sum  = "+sum); 
}

instead of going through all the numbers from 2 to i I just go from 2 to sqrt(i) and this improve your code running time a lot :)


@Lrrr, answer is correct. But algorithm can be further optimised. Look at my isPrime algorithm. For 2 million you don't need the BigInteger.

    long sum = 2;// new BigInteger("2");
    for (int i=3; i<2000000; i++) {
        if(isPrime(i)) {
            sum = sum + i;//.add(BigInteger.valueOf(i));
        }    
    }
    System.out.println("Sum  = "+sum);

Here is isPrime method.

 static boolean isPrime(int n) {
    if (n < 2) {
        return false;
    }
    if (n == 2 || n == 3) {
        return true;
    }
    if ((n & 1) == 0 || n % 3 == 0) {
        return false;
    }
    int sqrtN = (int) Math.sqrt(n) + 1;
    for (int i = 6; i <= sqrtN; i += 6) {// loop 6 step
        if (n % (i - 1) == 0 || n % (i + 1) == 0) {
            return false;
        }
    }
    return true;
}

You could use Sieve of Eratosthenes algorithm, it is more efficient then yours.

1) Store all numbers between 2 and N in array and mark them all as prime numbers.

2) Start from X = 2, and mark all its i*X (2X, 3X..), where i is natural number less then or equal N, multipliers as not prime. Do not mark X.

3) Find the next number greater then X which is not marked and repeat the procedure. If there is no such number, stop.

4) Remaining numbers in your array are prime

Something like this:

public static boolean[] findPrimes (int N) {

    boolean[] primes = new boolean[N + 1];

    // assume that all numbers are prime within given range
    for (int i = 2; i <= N; i++) {
        primes[i] = true;
    }

    // for all numbers in range, starting from 2
    for (int i = 2; i*i <= N; i++) {

        // mark natural multiples of i as nonprime
        if (primes[i]) {
            for (int j = i; i*j <= N; j++) {
                primes[i*j] = false;
            }
       }

 return primes;
}

5) Iterate over returned primes and sum indexes of TRUE values