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 ]

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

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: