Project Euler Problem #50

May 19, 2010

Read the details of the problem here

Summary

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

Solution

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
        len++
        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.)

Conclusion

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.

Advertisements

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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: