Project Euler Problem #50

May 19, 2010

Read the details of the problem here


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


Another straightforward brute-force solution. Just generate a list of primes (using the usual sieve to start with) and then see what prime values can be attained by adding up subsequent primes whilst remaining under the limit. Keep track of the maximum prime found and that’s that.

def LIMIT = 999999
def SQRT_LIMIT = (int)Math.sqrt(LIMIT)

def isPrime = new boolean[LIMIT+1]
Arrays.fill(isPrime, true)
(0..1).each { isPrime[it] = false }

for (i in 2..SQRT_LIMIT) {
    if (!isPrime[i]) continue
    def j = i + i
    while (j < LIMIT) {
        isPrime[j] = false
        j += i

def primes = (2..LIMIT).findAll { isPrime[it] }

def ( max, answer ) = [ 0, 0 ]

primes.eachWithIndex { prime, idx ->
    def ( len, sum ) = [ 1, prime ]
    for (i in idx+1..<primes.size()) {
        sum += primes[i]
        if (sum > LIMIT) break
        if ((len > max) && isPrime[sum]) (max, answer) = [ len, sum ]

This runs in 1.93 seconds with the construction of the sieve & prime list taking 1.14 seconds (59%) of that. A Java version completes in 0.12 seconds – only 6x faster as there is a lot of work being done in the Collections libraries in both versions. As they both use Lists for the primes there’s a lot of Integer auto-(un)boxing going on during processing. (Loading the primes into a native int-array drops the Java run time down to a much more respectable 34 ms.)


Groovy made it nice & easy to construct the list of primes from the sieve in a declarative manner, although an explicitly coded loop would be faster. I used an eachWithIndex()

closure for the outer loop but, as I wanted to be able to break out of the inner loop when values exceed the limit, I had to use a normal for-loop there (as I didn’t want to have to use Exceptions to do it). The transparent use of lists in Groovy always makes for a terse syntax.


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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

%d bloggers like this: