ProjectEuler.net problem #50, Consecutive Prime Sum

Question

I am trying to solve ProjectEuler.net problem #50, Consecutive Prime Sum. Here is the problem:

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

I have written some code which solve the problem just fine when the limit is 10, 100, 1000 or 10000 but when the limit is 1000000 as the problem requires, the program takes too much time to finish running!!

What can be done to my code to make the program faster?

package com.company;
import java.util.ArrayList;

class ConsecutivePrimeSum {
    public static int limit=1000000;
    int lengthOfTheLongest =0;
    int sumOfTheLongest =0;


    void solution(){
        ArrayList<Integer> arrayOfPrimes=generatePrimes();
        scanSequences(arrayOfPrimes);
        System.out.println("The longest sum is "+ sumOfTheLongest +"  and contains "+lengthOfTheLongest+" terms");
    }
    private ArrayList<Integer> generatePrimes(){
        ArrayList<Integer> arrayOfPrimes=new ArrayList<Integer>();
        for(int i=limit;i>=2;i--){
            if(isPrime(i)){
                arrayOfPrimes.add(i);
            }
        }
        return arrayOfPrimes;
    }

    /**
     * @param s
     * this scans ArrayList s, to get sequence of prime numbers and calculate
     * their sum and corresponding length
     * then assign the longest length to the variable lengthOfTheLongest, and its sum to variable sumOfTheLongest
     */
    private void scanSequences(ArrayList<Integer> s){
        ArrayList<Integer> cumulativeSums=generateCumulativeSums(s);
        for(int start=1;start<=s.size();start++){
            for (int end=s.size()-1;end>=start;end--){
                if(!isPrime(sumFromTo(cumulativeSums,start,end)))  continue;
                if(sumFromTo(cumulativeSums,start,end)>limit) break;
                if ((end-start+1)> lengthOfTheLongest){
                    sumOfTheLongest =sumFromTo(cumulativeSums,start,end);
                    lengthOfTheLongest =(end-start+1);
                }
            }
        }

    }

    /**
     * @param s
     * @return arraylist of cumulative sums of the elements in s
     */
    private ArrayList<Integer> generateCumulativeSums(ArrayList<Integer> s){
        int sum=0;
        ArrayList<Integer> cumulativeSums=new ArrayList<Integer>();
        for (int i=0;i<s.size();i++){
            cumulativeSums.add(sum=sum+s.get(i));
        }
        return cumulativeSums;
    }

    /**
     * @param a is an ArrayList whose elements are to be summed
     * @param start is the index of where summing should start
     * @param end is the index of where summing should end
     * @return the obtained sum
     */
    private int sumFromTo( ArrayList<Integer> a,int start, int end){
        int sum;
        sum=a.get(end)-a.get(start-1);
        return sum;
    }

    private static boolean isPrime(int number){
        boolean isPrime=false;
        int divider=2;
        int count=0;
        while(divider<=number){
            if(number%divider==0)
                count=count+1;
            divider=divider+1;
        }
        if(count==1)
            isPrime=true;

        return isPrime;
    }


}
class Test{
    public static void main(String [] args){
        ConsecutivePrimeSum consecutivePrimeSum=new ConsecutivePrimeSum();
        consecutivePrimeSum.solution();
    }
}

Answer 1

• Generation of prime numbers is suboptimal. Use a sieve of Erathosthenes.

• isPrime is highly suboptimal. You already generated an array of all necessary primes, so just binary search it.

• Breaking the loop in

          if(sumFromTo(cumulativeSums,start,end)>limit)
              break;
  

  looks like a bug. The intention is to loop by decreasing end, yet since the loop starts with the very long sequence, its sum is likely to exceed the limit right away. Shorter sequences with the same start are never tested.

  Consider finding the proper end as an upper limit of a sumFromTo(cumulativeSums, start, end) <= limit predicate (hint: another binary search).

• You are not interested in all sequences of the primes. Most of the primes execs 2 are odd. Notice that if the sequence has an even number of odd primes, its sum is even, that is not a prime. Once the correct end is established, you may safely decrease it by 2.

• Style wise, give your operators some breathing space.

      for (int end = s.size() - 1; end >= start; end--) {
  

  is much more readable than

      for (int end=s.size()-1;end>=start;end--){
  

PS: I am not aware of any math regarding sums of consecutive primes. It is very much possible that such math exists, and the goal of this problem is to discover it. That would be a true optimization.

Answer 2

Prime Generation

As mentioned by vnp, use the Sieve of Eratosthenes. In that implementation, use a BitSet(1_000_000) for efficient memory usage during your sieve; a sieve for primes up to one million will only take 125 KB of memory.

Keep the sieve around after you've generated your prime numbers, because it makes a very efficient \$O(1)\$ time complexity isPrime(number) checker:

bool isPrime(int number) {
    return sieve.get(number);
}

Prime Generation, Part 2

How many primes numbers are there (less than one million)? You don't know, so you've used an ArrayList<Integer> to store them.

But you could know. It will be sieve.cardinality(). So instead of using a memory wasting, slow-to-access indirect container, you could use:

int[] arrayOfPrimes = new int[sieve.cardinality()];

which gives you a much smaller memory footprint, and faster access speeds.

Ditto for your cumulativeSums. You could even make these a long[], to avoid possible overflows, and still use less memory than ArrayList<Integer> will!

Longest Sequence

What is the longest sequence of primes that sum to any value (prime or not) less that one million? This will be your absolute limit for the length of the sequence. Any sequence longer than this is pointless to check.

The longest sequence that sums to a value less than one million will, of course, contain the smallest values. So, it will be:

2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + ... + prime[n-1]

So just start adding the prime numbers until it exceeds one million; that number of terms is the limit. Your search space is only sequences between 21 terms and this limit in length. And if you search backwards, you can stop when you find the first working value.

Even & Odd length sequences

The sum of an even number of odd numbers is even, so cannot be prime. The only way to make an odd number, using an even number of primes is if one of those primes is even (2), so the remaining primes compose an odd number of odd numbers.

Ergo:

• Even length sequences must start at 2 (2 + 3, 2 + 3 + 5 + 7, ...)
• Odd length sequences must not start at 2.

So an even length sequence check could be a quick check of isPrime(cumulativeSum[n]). No loop required.

Odd length sequences still need to check isPrime(cumulativeSum[i+n] - cumulativeSum[i]) for all i, (for differences less than one million, of course).

Answer 3

I realize that this is old, but I just happened to see it today and no one else is making these points.

As others have already noted, finding all primes up to a value is a task well suited for the Sieve of Eratosthenes. So you may not need a method to check if a number is prime by trial division at all. But there are problems where determining primality via trial division is useful. And this method is not an optimal approach.

    private static boolean isPrime(int number){
        boolean isPrime=false;

You don't need the isPrime boolean. You can always just return instead.

Incidentally, isPrime would normally be considered a method name in Java. So just prime (or perhaps result) would be a more common name here. But unnecessary in this case.

        int divider=2;

Later, I'm going to replace the while loop with a for loop, so this declaration will move into the loop.

        int count=0;

You count all the factors of a number from two to the number itself. This is excessive. If you find a single factor more than one and less than the number itself, then the number is prime. You can return right then. So you don't need a count variable.

        while(divider<=number){
            if(number%divider==0)
                count=count+1;
            divider=divider+1;
        }

Consider

        if (number % 2 == 0) {
            return false;
        }

        for (int candidate = 3; candidate <= number / candidate ; candidate += 2) {
            if (number % candidate == 0) {
                return false;
            }
        }

Factors always come in pairs. At least one member of the pair must be less than or equal to the square root of the number. So you can stop checking when the number is greater than its complement. Because if you check from smallest to largest, you would have already found one member of the pair.

If the number is not divisible by two, then it is not divisible by any even number. So it's a waste to check if it is divisible by even numbers greater than two. This special cases two and then only checks odd numbers thereafter.

I prefer the name candidate over divider (or the more mathematical word: divisor). We are testing candidates to see if they are factors. If you want to be more explicit, consider candidateFactor.

        if(count==1)
            isPrime=true;

        return isPrime;
    }

This could be simpler as

        return count == 1;
    }

That has exactly the same result but is three lines of code shorter (counting the unnecessary declaration and initialization of isPrime).

But if we return false as soon as we find a factor, this can be even simpler:

        return true;
    }

One answer suggested that you could binary search your list of primes to implement isPrime. That would work, but it may not be as fast as storing the primes in either a HashSet or a LinkedHashSet rather than a List. Of course, if you generate the primes with a sieve, that will leave you with an efficient data structure for querying primality (also already suggested).