0
\$\begingroup\$

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();
    }
}

```
\$\endgroup\$
  • \$\begingroup\$ Hello, this question is off-topic, since the code is not working as intended; I suggest that you read the What topics can I ask about here? Code Review aims to help improve working code. If you are trying to figure out why your program crashes or produces a wrong result, ask on Stack Overflow instead. Code Review is also not the place to ask for implementing new features. \$\endgroup\$ – Doi9t Mar 21 at 14:18
  • 2
    \$\begingroup\$ @Doi9t Improving performance questions are on topic here. The code apparently works as intended for smaller limits. \$\endgroup\$ – vnp Mar 21 at 22:02
  • \$\begingroup\$ What are your ideas for a better algorithm? \$\endgroup\$ – greybeard Mar 22 at 0:22
  • 1
    \$\begingroup\$ The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How do I ask a good question? for examples, and revise the title accordingly. \$\endgroup\$ – Martin R Mar 22 at 1:27
6
\$\begingroup\$
  • 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ That would be a true optimizationWouldn't it? \$\endgroup\$ – greybeard Mar 22 at 0:17
  • \$\begingroup\$ @greybeard Perhaps, if only they'd spell some math. \$\endgroup\$ – vnp Mar 22 at 2:03
3
\$\begingroup\$

Prime Generation

As mentioned by vnp, use the Sieve of Eratosthenese. 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).

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.