## 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.