Project Euler Problem #47

April 24, 2010

Read the details of the problem here


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


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]++ }

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


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


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: