Project Euler Problem #77

September 4, 2010

Read the details of the problem here


What is the first value which can be written as the sum of primes in over five thousand different ways?


Straightforward and quick to solve using the solutions to Problem #31 and Problem #76 as a starter. The values of primes just replace the values of coins from Problem #31. It’s a quick hack to wrap it in a loop that increments total and selects a suitable list of primes to work with on each iteration.

def primes =
    (1..<100).findAll { new BigInteger(it).isProbablePrime(100) }

def ( answer, total ) = [ 0, 11 ]

while (!answer) {

  def nways = [1] + [0]*total

  primes.findAll { it < total }.each { prime ->
    prime.upto(total) { nways[it] += nways[it - prime] }

  if (nways[total] > 5000) answer = total

This runs in 190 ms. It’s not the most efficient of algorithms but it’s well within my 15 seconds target. The length of the prime list was arbitrary but sufficient.


Groovy’s listops made the solution terse to write but nothing that couldn’t be done in normal Java.


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 )

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: