Euler Problem 50

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?

This took a while to solve partly because I went on vacation and partly because I was being a stubborn bonehead.

I initially tried to solve for all possible starting positions. It worked but I soon discovered it would take days to solve. Wanting to avoid using brute force, I instead went about being a smart ass and used a complicated sifter technique. Needless to say it didn’t work very well.

So, I went back to my original algorithm (which works — see below) dropped the starting position to the first 10 rather than the first 500K. Voila: solved in 12 seconds.

import java.util.*;

public class Euler50
{
    public static void main(String[] args)
    {
        Euler50 e = new Euler50();
        System.out.format(“Problem: %s\n”, e.getClass().getName());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<Integer> P = new ArrayList<Integer>();
        P = makePrimes(1000000);
        int maxTerms = 0, maxSum = 0, sum = 0, count = 0;
        for (int p: P)
        {
            for (int i = 0; i < 10 ; i++)
            {
                count = 0;
                sum = 0;
                for (int n = i; P.get(n) < p/2; n++)
                {
                    sum += P.get(n);
                    count++;
                    if (sum > p)
                        break;
                    if (sum == p)
                    {
                        if (count > maxTerms)
                        {
                            maxTerms = count;
                            maxSum = sum;
                            System.out.format(“sum:%d, terms:%d\n”, sum, count);
                        }
                    }
                }
            }
        }
        return String.valueOf(maxSum);
    }
    public ArrayList<Integer> makePrimes (int lim)
    {
        ArrayList<Integer> P = new ArrayList<Integer>();
        boolean [] isPrime = new boolean [lim+1];
        for (int i = 2; i < lim; i++)
            isPrime[i] = true;
        for (int p = 2; p*p < lim; p++)
            if (isPrime[p] == true)
                for (int m = p*p; m < lim; m = m+p)
                    if (m % p == 0)
                        isPrime[m] = false;
        for (int i = 2; i < lim; i++)
            if (isPrime[i])
                P.add(i);
        return P;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s