Euler Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Use a prime number generator (from earlier) and an accumulator.

Update: My first attempt failed. Brute force generator from earlier problem took 33 minutes to generate the sum, but the number was off. So I’ll need to refine the algorithm. Found this on Wikipedia:

To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

1. Create a list of consecutive integers from two to n: (2, 3, 4, …, n),
2. Initially, let p equal 2, the first prime number,
3. While enumerating all multiples of p starting from p², strike them off from the original list,
4. Find the first number remaining on the list after p (it’s the next prime); let p equal this number,
5. Repeat steps 3 and 4 until p² is greater than n.
6. All the remaining numbers in the list are prime.

Works like a dream and fast!

public class Euler10
{
    public static void main(String[] args)
    {
        System.out.print(“Problem 10:\n”);
        Euler10 e = new Euler10();
        System.out.print(“Answer = ” + e.Problem()+ “\n”);
    }
    public String Problem ()
    {
        long accumulator=0;
        int n = 2000000;
        boolean [] isPrime = new boolean [n+1];
        for (int i = 2; i < n; i++)
        {
            isPrime[i] = true;
        }
        for (int p = 2; p*p < n; p++)
        {
            if (isPrime[p] == true)
            {
                for (int m = p*p; m<n; m=m+p)
                {
                    if (m % p == 0)
                    {
                        isPrime[m] = false;
                    }
                }
            }
        }
        for (int i = 2; i < n; i++)
        {
            if (isPrime[i] == true)
            {
                System.out.print(i+”\n”); //remove to speed up
                accumulator += i;
            }
        }
        return String.valueOf(accumulator);
    }
}