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 p2, 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 p2 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);
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s