## Project Euler Problem #77

### September 4, 2010

Read the details of the problem here

Summary

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

Solution

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 ]

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

Conclusion

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