0x000c - Project Euler 010

Problem:

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

Find the sum of all the primes below two million.

Solution:

1. Brute-force approach:

class PE010_brute
{
    static boolean isPrime(long n)
    {
        if(n == 2 || n == 3) return true;
	if(n < 2 || (n % 2 == 0)) return false;
        if(n < 9) return true;
        if(n % 3 == 0) return false;

        int r = (int)Math.sqrt(n), f = 5;

        while(f <= r) {
            if ((n % f == 0) || (n % (f + 2) == 0))
                return false;
            f += 6;
        }
        return true;
    }
}

2. Efficient approach (using the Sieve of Eratosthenes) :

class PE010
{
	public static void main(String args[])
	{
		int limit = 2000000;
		int crosslimit = (int)Math.sqrt(limit);
		boolean[] sieve = new boolean[limit];
		int m, n;

		for(n = 4; n < limit; n += 2)
			sieve[n] = true;

		for(n = 3; n <= crosslimit; n += 2)
			if(!sieve[n])
				for(m = n*n; m < limit; m += 2*n)
					sieve[m] = true;

		long sum = 0;
		for(n = 2; n < limit; n++)
			if(!sieve[n])
				sum += n;

		System.out.println(sum);
	}
}

Analysis:

The brute force approach uses the Method 5 explained in this post on primality testing. We assign the upper bound of 2 million to the variable limit. Then, starting from 3, we add up all odd numbers which satisfy the isPrime() method, with the result being stored in the long variable sum. The initial value of sum is 2 as we don’t need to check primality of 2. Finally, the sum of all primes below 2 million is printed to the standard output.

The second approach uses the Sieve of Eratosthenes to get an array of all primes below 2 million. The entire algorithm is explained in this post. The upper bound is stored in the integer variable limit and the boolean array sieve[] stores the list of primes below limit. After finding all the primes, we add them up and save the result in the long variable sum, which is then printed to the standard output.

Running time:

1. Brute-force approach: 1464 milliseconds
2. Efficient approach: 20 milliseconds, which is 1.366% of the time taken by the brute-force approach (more than 73 times faster). Also, the Sieve of Eratosthenes algorithm has a time complexity of just O( n.log(log(n) ), which is much better than the naive primality test applied in the first approach.