0
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Safe to presume Helper.getPrimes(1000000) returns all primes under 1000000? \$\endgroup\$ – h.j.k. Jun 3 '15 at 9:41
  • \$\begingroup\$ @h.j.k. yes. maybe it's obvious. maybe not \$\endgroup\$ – RE60K Jun 3 '15 at 9:42
  • \$\begingroup\$ How long does Helper.getPrimes(1000000) take on its own? \$\endgroup\$ – Ben Aaronson Jun 3 '15 at 9:54
  • \$\begingroup\$ @BenAaronson Time taken 0.101968274 seconds \$\endgroup\$ – RE60K Jun 3 '15 at 10:06
2
\$\begingroup\$

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));
    }
}
\$\endgroup\$
2
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ I could bring it to Answer is 997651, Time taken 10.662135044 seconds after converting ArrayList to int[]. Nothing else helps. +1... \$\endgroup\$ – RE60K Jun 3 '15 at 13:51
  • \$\begingroup\$ @ADG Then I guess that your Helper.isPrime is the culprit. Just a guess. What about a boolean[] (created from the prime list) for a faster test? \$\endgroup\$ – maaartinus Jun 3 '15 at 15:16
  • \$\begingroup\$ my helper.isPrime is done using boolean[] only. \$\endgroup\$ – RE60K Jun 3 '15 at 16:44
  • \$\begingroup\$ @ADG Then I'm lost. Maybe replace 1e6 by an int? I've just added my loop body to the answer. \$\endgroup\$ – maaartinus Jun 3 '15 at 17:10
  • 1
    \$\begingroup\$ @ADG Partly. Your original code with my PrimeHelper takes 2241 ms on my computer. 2 GB is plenty for this, but the CPU is rather weak. Now, I see the problem: You find the solution about as fast and I do and then you spend a lot of time in computing sum for each len albeit it gets too big after the first few terms. Add the test in the i loop or use my precomputed long[] sums. \$\endgroup\$ – maaartinus Jun 3 '15 at 18:02
1
\$\begingroup\$

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;
                    }
        }                   
    }
}
\$\endgroup\$
  • \$\begingroup\$ yes you're right. Answer is 997651, Time taken 10.662135044 seconds is the closest call to your python and because you're having prime method more expanded (expanded, maybe not the right word to use) it would improve by 2-3 secs? \$\endgroup\$ – RE60K Jun 3 '15 at 13:52

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.