Project Euler #10 -- Summation of primes takes forever

Question

I have resolved the Problem presented in Project Euler #10:

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

Find the sum of all the primes below two million.

But this code takes too long before producing a result, 12.4195167 minutes to be exact.

What should I do to optimize this code?

public class summationOfPrimes{
public static void main(String args[]){
    long sum=0;
    outerloop:
    for(int i=2;i<2000000;i++){
        for(int j=2;j<=i;j++){
            if(i!=j&&i%j==0){
                continue outerloop;
            }
            else if(j==i){
                sum=sum+i;
            }
        }
        
    }
    
    System.out.println(sum);
    
}

}

Answer 1

Well, let's start with a few optimizations for you:

• Any i that is a multiple of 2 but not 2, is not a prime. Consider upping i by 2 at a time, and starting sum off at 2. i would start at 3.
• If something is divisible by 4, it's divisible by 2. Therefore, it's a good idea to make j iterate through a list of already found primes - it's no use testing if something is divisible by 4 if it's not divisible by 2.
• 3*3 = 9. When you are checking whether a certain i is a prime, you can stop at the point where j*j is greater than the prime to test. For 7, you can stop at 3; 3*3 = 9, after all.

Answer 2

I'll start with the easy stuff: You are violating multiple java code-conventions. While this doesn't necessarily improve performance, you should still do that, simply because it makes understanding (and thus possibly optimizing) the code much easier:

public class summationOfPrimes{
public static void main(String args[]){

for starters, convention states that typenames should start with an uppercase letter. Additionally everything in braces should be indented by one level.

    for(int i=2;i<2000000;i++){
        for(int j=2;j<=i;j++){
            if(i!=j&&i%j==0){

These numbers and operators could use a little more space to breathe, simply because they are easier to spot then:

    for (int i = 2; i < 2_000_000; i++) {
        for (int j = 2; j <= i; j++) {
            if (i != j && i % j == 0) {

Additionally you're using lots and lots of excess newlines near the end of main.. remove them ;)

Answer 3

I would recommend using a Sieve instead of trial division each time. If you find 3 is prime, then 6, 9, 12....you will know are composite. So if you make a giant list of "primes" (All numbers 1 through N for starters) and then start knocking out multiples of primes, you'll be left with a list of real primes.

Here is an example code using a boolean array. (True indices are composite, false means they are prime. So if array[5] is false, it's prime, whereas array[1000000] is true)

Running time is roughly 0.09 seconds on an online Java interpreter. This method is known as the Sieve of Eratosthenes.

public static boolean[] simpleSieve(int n)
{
    boolean[] sieve = new boolean[n+1];  //false = prime, true = composite
    sieve[0] = true; sieve[1] = true; sieve[2] = false;

    for(int i = 4; i <= n; i+=2)
    { sieve[i] = true; }

    int limit = (int)Math.sqrt(n)+1;
    for(int i = 3; i < limit; i+=2)
    {
        if(!sieve[i]) //if prime (or not composite)
        {
            for(int j = i*i; j <= n; j+=i) //mark all multiples of i as composite
            { sieve[j] = true; }
        }
    }

    return sieve;
}

First loop knocks out the even numbers, since 2 is the ONLY even prime. The second loop knocks out the odd numbers, up to the square root of N. After the square root of N, there are no more multiples or composites left. Whatever is left after the square root of N is a prime entry.

So with an array saying "here is what is prime and not prime", you just need to add them up.

public static long sumOfPrimes(int n)
{
    //get primes
    boolean[] primes = simpleSieve(n);
    long sum = 0;

    for(int i = 0; i < primes.length; i++)
    {
        if(!primes[i])
        { sum += i; }
    }

    return sum;
}

And to get your result, you simply print the result of that method.

public static void main (String[] args) throws java.lang.Exception
{
    System.out.println(sumOfPrimes(2_000_000));
}

This algorithm needs a tweak for Lists or some other data structure for larger values, since arrays can only have an integer for their indices. Though if you were going for finding primes up to 2,147,483,647 then this method may consume more memory than you have on hand.

But for Project Euler's solution this should still be useful.

As per David's comment, it is mentioned that using BitSet is a more memory efficient way of storing the bit flags for primes & composites, and this allows for a higher limit of how much we can store and calculate. Though eventually the long used for the summation of primes will overflow as you use higher values, so switching to BigInteger would be needed there, and even larger versions require a segmented sieve and/or larger data structure.

Revised BitSet friendly functions:

public static BitSet simpleSieve(int n)
{
    BitSet sieve = new BitSet(n+1); //New BitSet
    sieve.set(0); sieve.set(1);     //0 & 1 aren't primes, set their bits

    for(int i = 4; i <= n; i+=2)  //set all multiples of 2
    { sieve.set(i); }

    int limit = (int)Math.sqrt(n)+1;

    for(int i = 3; i < limit; i+=2)
    {
        if(!sieve.get(i)) //if prime (or "not composite")
        {
            for(int j = i*i; j <= n; j+=i) //mark all multiples of i as composite
            { sieve.set(j); }
        }
    }

    return sieve;
}

public static long sumOfPrimes(int n)
{
    //get primes
    BitSet primes = simpleSieve(n);
    long sum = 0;

    for(int i = 0; i < n+1; i++)
    {
        if(!primes.get(i)) 
        { sum += i; }
    }

    return sum;
}

Answer 4

Euler project problems are best optimized using a different algorithm, the double for loop leads to O(n^2) while it can be much faster using a sieve method. I'll be keeping an array of all already found primes to test against.

Besides that the inner loop should only run while j*j <= i (if there was a larger number that divides i then we would have found i/j first) and put the sum part out of the inner loop:

The i==j if is true once in the inner loop at the final iteration, you can then move the code to the outer loop after the inner for.

Using the array:

int[] primes = new int[100000];
int biggestPrimeIndex = 0;
outerloop: for(int i=2; i<2000000; i++){
    for(int j=0; j<biggestPrimeIndex ; j++){
        if(i % primes[j] == 0){
            continue outerloop;
        }
    }
    if(biggestPrimeIndex==primes.length)
        primes = Arrays.copyOf(primes, biggestPrimeIndex*2);

    primes[biggestPrimeIndex++] = i;
    sum = sum+i;
}

I also adjusted the spacing a bit.

Answer 5

Try to avoid putting all your code in main.

public static void main(String args[]){
    System.out.println(sum(generatePrimesUpTo(2000000)));
}

By writing it this way, it just holds the input to generate (two million in this case; ten in the original example). You can write a generic, reusable sum function:

public static long sum(List<Integer> numbers) {
    long sum = 0L;

    for ( Integer number : numbers ) {
        sum += number;
    }

    return sum;
}

Then you just need a generatePrimesUpTo function:

private static List<Integer> generatePrimesUpTo(int maximum_value) {
    if ( 3 > maximum_value ) {
        throw new IllegalArgumentException();
    }

    List<Integer> primes = new ArrayList<Integer>(Arrays.asList(2, 3));

    int increment = 4;
    for ( Integer i = 5; i <= maximum_value; i += increment ) {
        boolean isPrime = true;

        for ( Integer prime : primes ) {
            if ( 0 == i % prime ) {
                isPrime = false;
                break;
            }

            if ( prime * prime > i ) {
                break;
            }
        }

        if ( isPrime ) {
            primes.add(i);
        }

        increment = 6 - increment;
    }

    return primes;
}

This is the same basic idea as your function, but it saves time by only trying to divide by other primes.

Let's go through some of the pieces.

private static List<Integer> generatePrimesUpTo(int maximum_value) {

Our method takes a maximum value and generates a list of primes up to (and including) that number.

    if ( 3 > maximum_value ) {
        throw new IllegalArgumentException();
    }

We optimize the method to only work for maximum values of three or more. If we get less than that, we throw an exception.

    // primes needs to be an implementation that returns elements in insertion order
    // since we stop checking when it grows larger than the square root of the current candidate
    List<Integer> primes = new ArrayList<Integer>(Arrays.asList(2, 3));

We initialize our list of primes with 2 and 3. The reason is that 2 is the only even prime and 3 is the only prime divisible by three. So we know that no greater even number will be prime and that every third odd number won't be.

    int increment = 4;
    for ( Integer i = 5; i < maximum_value; i += increment ) {
        increment = 6 - increment;
    }

We take advantage of that by starting with 5. Then we add two (6 - 4) to get seven. Then four (6 - 2) to get eleven. This skips nine, which is divisible three. We alternate incrementing by two and four thereafter.

In case you haven't seen it previously, i += increment is a shorter way of writing i = i + increment.

            if ( prime * prime > i ) {
                break;
            }

This is cheating a bit. Because primes is an ArrayList, we know that its iterator() will return the values in insertion order. So we know that all remaining elements of primes will be larger than prime.

Answer 6

Project Euler problems usually need a bit of thinking to get a fast solution. Your code has two problems that make it slow.

One, your code to check whether an integer i is a prime or not is slow. A number i ≥ 2 is prime by definition if it has no divisors other than 1 and itself. You look for a divisor j, 2 ≤ j ≤ i - 1. However, you only need to check numbers where j * j ≤ i: If j is a divisor, then i / j is also a divisor. If j is the smallest divisor, then i / j is also a divisor and i / j ≥ j (because j is the smallest divisor). That means i = j * (i / j) ≥ j * j. So after checking the values j where j * j ≤ i you would have found the smallest divisor. You didn't find one, so i is a prime.

Two, your code checks each number individually. But you want all primes from 1 to two millions, so you should check if there is a faster method. And there is one: On a piece of paper, you could write down the numbers from 2 to two million. Then remove all the numbers that are multiples of two except the number two itself (4, 6, 8, 10, ...). Then remove all the numbers that are multiples of three except the number 3 itself (6, 9, 12, 15, ...; but the even numbers have already been removed so you just remove 9, 15, 21, 27 ... ), then the multiples of five except five itself (that would be 15, 25, 35, 45 ignoring the even numbers, but 15 was already removed as a multiple of 3, so you start at 5 * 5) and so on.

Why is this faster? You might have divided for example several hundred thousand numbers by 89. But with this method, you just remove every one in 178 numbers; much less work.