Project Euler Problem #47

April 24, 2010

Read the details of the problem here

Summary

Find the first four consecutive integers to have four distinct primes factors.

Solution

Easy enough. Just use a simple sieve (as we’re not actually interested in what those factors are) to count the number of prime factors for any particular number, looking backwards to see if the last four (including the current one) have the requisite number of factors.

def (f, i) = [ [0] * 1e6, 2 ]

while ((0..3).any { f[i-it] != 4 }) {
  if (f[i] == 0) (i+i).step(f.size(),i) { f[it]++ }
  i++
}

def answer = i - 3

This runs in 3.85 seconds. The size of the sieve is somewhat arbitrary, it just assumes that the answer will be found within a 6-digit range – in fact, in under 500000 due to the (i+i).step(…) statement which would run backwards otherwise! A version that avoid the use of Groovy lists and listops and uses more conventional while-loops run in 1.12 seconds. A Java version runs in…well, it’s just embarrassing…14 ms (so 80x faster).

Conclusion

Again, Groovy provides a quick time-to-solution but at a considerable overhead for the actual runtime.

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: