Sum of primes using Sieve of Eratosthenes; answer too small

Question

For Project Euler problem #10, I wrote a program to find the sum of all prime numbers between 2 and 2,000,000.

My code works for smaller values like 50 or 100, but when I try it with 2,000,000 it returns a value that is too small by 141,675.

I thought it might be because the answer was too long to fit in a long, which is why I use BigInteger, but I've since learned that's not a factor. I appreciate any thoughts.

public class ProblemTen {


/**
 * Precondition:  all the bits in the set are set to true
 * This method uses the Sieve of Eratosthenes
 * @param p the starting prime number
 * @param b the BitSet array
 * @param s the length of the original BitSet array
 * @return BitSet with all the prime indexes set to true
 */
public static BitSet findPrimes(int p, BitSet b, int s) {
    //System.out.println(b);
    while (p*p < s) {  // repeat until p^2 > size of the ORIGINAL set 
        for (int i = 0; i <= b.length(); i++) {
            if (i%p == 0) { // if it's a multiple of p
                b.set(i, false); // set it to false (not prime)
            }
        }
        p = b.nextSetBit(p); // Make p = first bit that is set to true starting after the previous p index.
    }
    return b;
}

/**
 * @param args
 */
public static void main(String[] args) {

    int set = 2000000;

    BitSet bits = new BitSet(set);
    for (int i = 0; i < set; i++) {
        bits.set(i); // set all bits to True; when you print only the true ones print out
    }
    BitSet primeBits = new BitSet(set);
    primeBits = findPrimes(2, bits, set);
    //System.out.println("List of primes: " + primeBits);

    BigInteger sum = BigInteger.ZERO;
    for (int j = 0; j <= primeBits.length(); j++) {
        if (primeBits.get(j) == true ) {
            sum = sum.add(BigInteger.valueOf(j));
        }
    }

    System.out.println("Sum is: " + sum); // I get 142,913,687,247 which is 141,675 too small (142913828922)
}

}

Answer 1

    while (p*p < s) {  // repeat until p^2 > size of the ORIGINAL set 
        for (int i = 0; i <= b.length(); i++) {
            if (i%p == 0) { // if it's a multiple of p
                b.set(i, false); // set it to false (not prime)
            }
        }
        p = b.nextSetBit(p);
        // Make p = first bit that is set to true starting after the previous p index.
    }

Marks all multiples of the prime p as composite, including p itself. So only the primes larger than the square root of the limit remain unmarked.

• This method uses the Sieve of Eratosthenes

No, it doesn't. It uses trial division. You divide each number by all primes smaller than the square root of the limit and check whether the remainder is 0.

The loop should be

for(int i = p*p; i < b.length; i += p)
    b.set(i,false);

to implement the Sieve of Eratosthenes.

Answer 2

Your solution is not the Sieve of Eratosthenes, it's trial division; the modulo operator gives it away. Here is pseudocode for a proper Sieve of Eratosthenes that sums the primes that it finds:

function sumPrimes(n)
    sum := 0
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            sum := sum + p
            for i from p * p to n step p
                sieve[i] := False
    return sum

I'll leave it to you to translate the code to Java. If you are interested in programming with prime numbers, I modestly recommend this essay at my blog, which includes a Sieve of Eratosthenes in Java. The code there will also help you with some of the other Project Euler problems.

Answer 3

for (int i = 0; i <= b.length(); i++)

change it to

for (int i = p+1; i <= b.length(); i++)

Otherwise you're eliminating all primes smaller than 2,000,000^.5