Skip to content

Problem 47

May 14, 2010

Instead of building yet another function to calculate prime factors and sieves, I used an existing package: NumberTheory.Sieve.Factor to solve the 47th Euler problem:

import NumberTheory.Sieve.Factor

f l x = let l1 = zip l (map (length . factor (sieve x)) l)
            l2 = filter ((==) 4 . snd) l1
            l3 = consec l2
        in l3
  where consec (x1:x2:x3:x4:xs) =
          case (fst x4) - (fst x1) == 3 of
            True  -> [x1,x2,x3,x4]
            False -> consec (x2:x3:x4:xs)
        consec _ = []

main = print $ f [1..999999] 9999999

The function f calculates a list of pairs containing a number and the number of its prime factors, and filters all numbers that do not have 4 prime factors. Then it is a matter of calling the consec function, that returns the first 4 consecutive integers that have exactly 4 prime factors. The program executes in (0.38 secs, 143730392 bytes).

Advertisements
Leave a Comment

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: