Sum of maximum primes as another prime below a million

Question

This is a project Euler Problem #50. Here is my solution with 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?
 */
public static int get50() {
    int max = 21;
    int prime_max = 953;
    ArrayList<Integer> primes = Helper.getPrimes(1000000);
    for (int len = 21; len <= primes.size(); len += 2) {
        long sum = 0;
        if (primes.get(len - 1) > 1E6) {
            break;
        }
        if (sum > 1E6) {
            return prime_max;
        }
        for (int k = 0; len + k - 1 < primes.size(); k++) {

            if (k == 0) {
                for (int i = 0; i < len; i++) {
                    sum += primes.get(i);
                }
            } else {
                sum += primes.get(len + k - 1) - primes.get(k - 1);
            }
            if (primes.get(len + k - 1) > 1E6 || sum > 1E6) {
                break;
            }
            if (Helper.isPrime((int) sum)) {
                if (len > max) {
                    max = len;
                    prime_max = (int) sum;
                }
                break;
            }
        }
    }
    return prime_max;
}

Some things I wish to improve:

• Time (currently over 40 seconds, Answer is 997651, Time taken 43.762743956 seconds)
• If possible && If reduces time Then using the new Java 8 methods.This would help me learn it too.

Answer 1

Here's my take. It uses streams to get the prime numbers, but I didn't think it would have been very efficient to use streams in the actual calculation. I perform an optimization in putting the primes under a million in a set so that checking if the sum of the primes were itself a prime is simply checking if it is in the set. Not ideal from a memory standpoint, but it is certainly faster in this way.

This runs on my computer in 450 ms roughly, time to fetch the primes included.

public class BestConsecutiveSearch {
    private static final int MAX_VALUE = 1000000;

    private List<Integer> getPrimes(int max) {
        final List<Integer> primes = new ArrayList<>();
        IntStream.range(2, max+1)
                .filter(i -> { return isPrime(primes, i); })
                .forEach(primes::add);
        return primes;
    }

    private boolean isPrime(List<Integer> primes, int i) {
        double sqrtI = Math.sqrt(i);
        for(int p=0, prime; p < primes.size() && (prime=primes.get(p)) <= sqrtI; p++) {
            if (i % prime == 0)
                return false;
        }
        return true;
    }

    private int findLongestConsecutive(List<Integer> primes) {
        int bestSoFarCount = 0, bestSoFar = -1;
        Set<Integer> primeSet = new LinkedHashSet<>(primes);
        ListIterator<Integer> iterator = primes.listIterator();
        while(iterator.hasNext()) {
            int sum = 0;
            int currentIndex = iterator.nextIndex();

            ListIterator<Integer> secondIterator = primes.listIterator(iterator.nextIndex());

            while(sum < MAX_VALUE && secondIterator.hasNext()) {
                sum += secondIterator.next();

                if(sum < MAX_VALUE && primeSet.contains(sum) && secondIterator.nextIndex() - currentIndex > bestSoFarCount) {
                    bestSoFar = sum;
                    bestSoFarCount = secondIterator.nextIndex() - currentIndex;
                }
            }
            iterator.next();
        }   
        return bestSoFar;
    }

    public static void main(String args[]) {
        BestConsecutiveSearch search = new BestConsecutiveSearch();

        long startTime = new Date().getTime();
        List<Integer> primes = search.getPrimes(MAX_VALUE);
        System.out.println(search.findLongestConsecutive(primes));
        System.out.println("Total time: " + ((new Date()).getTime() - startTime));
    }
}

Answer 2

I've just switch my code from List<Integer> to int[] and the time went down from 19 to 11 seconds. This can be done using a loop or more simply with Guava's Ints.toArray().

While unboxing is cheap, you're needing it in the innermost loop. Which brings us to the point that there's no need for 3 nested loops, you're doing it right and I'm not. My code is faster, possibly because of my helper being faster...

public static int get50() {
    int max = 21;
    int prime_max = 953;
    ArrayList<Integer> primes = Helper.getPrimes(1000000);
    for (int len = 21; len <= primes.size(); len += 2) {

Use some constants... all those magic numbers in code are a pain. Btw., optimizing via the given values 21 and 953 saves about nothing.

Sometimes, a loop with decreasing len could be faster, but not here as the resulting length is close to the beginning.

    if (primes.get(len - 1) > 1E6) {

Again, constants please.

You could simplify the code by storing the partial sums and compute p[i] + p[i+1] + ... + p[j] simply as sum[j+1] - sum[i].

        if (primes.get(len + k - 1) > 1E6 || sum > 1E6) {

The first condition can never be true.

        if (Helper.isPrime((int) sum)) {
            if (len > max) {
                max = len;
                prime_max = (int) sum;
            }
            break;
        }

I'm not sure about the break, but I guess that's because of the resulting sum being unique for a given length.

If possible && If reduces time Then using the new Java 8 methods.This would help me learn it too.

I strongly doubt, using Java 8 features will help, though using Java 8 surely can, because of the new optimizations.

I did some similar optimizations to my code now and the resulting time is 440 ms, where the initialization of my prime helper takes 438 ms (it always sieves up to 128 million and it's hard to change).

---

As we don't know why is my code faster, I'm adding my loop body taking just a few milliseconds:

for (int len=1; len<primes.length; ++len) {
    for (int i=0; i<primes.length-len; ++i) {
        final int j = i+len;
        if (i>0 && (len&1) == 0) break;
        final long sum = sums[j] - sums[i];
        if (sum>limit) break;
        if (!helper.isPrime(sum)) continue;
        best = len;
        result = sum;
        break;
    }
}

Answer 3

I did it in Python (see my code below) some years ago. It runs in 9 seconds, but I think the same algorithm in C++ or Java could be very fast. Actually, I also wrote some "prime tools" in C++ since. I show you some interesting impementation for prime check below. There is probably better algorithms, but this one is enough for many problems.

Python code solving the problem :

import math
def isPrime(p):
    if p < 4:
        if p < 2:
            return False
        else:
            return True
    else:
        if p % 2 == 0:
            return False
        else:
            s = math.sqrt(p) + 0.1
            f = 3
            while f < s:
                if p % f == 0:
                    return False
                f += 2
            return True

def problem50(ubound):
    primes = [2]
    p = 3
    while p < ubound:
        if isPrime(p):
            primes.append(p)
        p += 2
    ibound = 0
    sum = 0
    while sum < ubound:
        sum += primes[ibound]
        ibound += 1
    max_k_found = 0
    max_p_found = 0
    kmax = 1
    k = 1
    while k < ibound:
        ibegin = 0
        while ibegin < ibound - k:
            sum = 0
            i = ibegin
            while i < ibegin + k:
                sum += primes[i]
                i += 1
            if isPrime(sum):
                if k > max_k_found:
                    max_k_found = k
                    max_p_found = sum
            ibegin += 1
        k += 1
    return max_p_found

print problem50(1000000)

Some C++ tools for prime numbers :

bool is_prime(long int n)
{
    if(n < 12)
        if(n < 6)
            if(n < 4)
                if(n < 2)
                    return false; // 0,1
                else
                    return true; // 2,3
            else
                if(n < 5)
                    return false; // 4
                else
                    return true; // 5
        else
            if(n < 8)
                if(n < 7)
                    return false; // 6
                else
                    return true; // 7
            else
                if(n < 11)
                    return false; // 8,9,10
                else
                    return true; // 11
    else  // n > 11
    {
        if(n % 2 == 0)
            return false;
        if(n % 3 == 0)
            return false;
        if(n % 5 == 0)
            return false;
        long int p = 7;
        while(true)
        {
            if(n % p == 0) return false;
            p += 4;
            if(p * p > n) return true;
            if(n % p == 0) return false;
            p += 2;
            if(p * p > n) return true;
            if(n % p == 0) return false;
            p += 4;
            if(p * p > n) return true;
            if(n % p == 0) return false;
            p += 2;
            if(p * p > n) return true;
            if(n % p == 0) return false;
            p += 4;
            if(p * p > n) return true;
            if(n % p == 0) return false;
            p += 6;
            if(p * p > n) return true;
            if(n % p == 0) return false;
            p += 2;
            if(p * p > n) return true;
            if(n % p == 0) return false;
            p += 6;
            if(p * p > n) return true;
        }
    }   
}

long int next_prime(long int n)
{
    if(n < 19)
        if(n < 7)
            if(n < 3)
                if(n < 2)
                    return 2;
                else
                    return 3;
            else
                if(n < 5)
                    return 5;
                else
                    return 7;
        else
            if(n < 13)
                if(n < 11)
                    return 11;
                else
                    return 13;
            else
                if(n < 17)
                    return 17;
                else
                    return 19;
    else
    {
        long int p = n;
        unsigned long int n_mod_30 = static_cast<unsigned long int>(n % 30);
        if(n_mod_30 < 13)
            if(n_mod_30 < 7)
                if(n_mod_30 < 1)
                {
                    p += 1;
                    n_mod_30 = 1;
                }
                else
                {
                    p += 7 - n_mod_30;
                    n_mod_30 = 7;
                }
            else
                if(n_mod_30 < 11)
                {
                    p += 11 - n_mod_30;
                    n_mod_30 = 11;
                }
                else
                {
                    p += 13 - n_mod_30;
                    n_mod_30 = 13;
                }
        else
            if(n_mod_30 < 23)
                if(n_mod_30 < 17)
                {
                    p += 17 - n_mod_30;
                    n_mod_30 = 17;
                }
                else if(n_mod_30 < 19)
                {
                    p += 19 - n_mod_30;
                    n_mod_30 = 19;
                }
                else
                {
                    p += 23 - n_mod_30;
                    n_mod_30 = 23;
                }
            else
                if(n_mod_30 < 29)
                {
                    p += 29 - n_mod_30;
                    n_mod_30 = 29;
                }
                else
                {
                    p += 2;
                    n_mod_30 = 1;
                }
        while(true)
        {
            if(is_prime(p))
                return p;

            if(n_mod_30 < 17)
                if(n_mod_30 < 11)
                    if(n_mod_30 < 7)
                    {
                        p += 6;
                        n_mod_30 = 7;
                    }
                    else
                    {
                        p += 4;
                        n_mod_30 = 11;
                    }
                else
                    if(n_mod_30 < 13)
                    {
                        p += 2;
                        n_mod_30 = 13;
                    }
                    else
                    {
                        p += 4;
                        n_mod_30 = 17;
                    }
            else
                if(n_mod_30 < 23)
                    if(n_mod_30 < 19)
                    {
                        p += 2;
                        n_mod_30 = 19;
                    }
                    else
                    {
                        p += 4;
                        n_mod_30 = 23;
                    }
                else
                    if(n_mod_30 < 29)
                    {
                        p += 6;
                        n_mod_30 = 29;
                    }
                    else
                    {
                        p += 2;
                        n_mod_30 = 1;
                    }
        }                   
    }
}