Skip to content

Problem 37

May 30, 2010

In the 37th Euler problem, I used the Hackage package containing the NumberTheory.Sieve.ONeill library in order to have access to an efficient infinite list of primes. Then it was a matter of manipulating lists to achieve the result.

import NumberTheory.Sieve.ONeill
import List
import Char

myElem (x:xs) n
  | n == x = True
  | n > x  = myElem xs n
  | n < x  = False

The myElem function searches a specific number in a sorted list (i.e. in the infinite prime list). Furthermore, it was a matter of defining the following functions:

g :: Int -> Bool
g n = foldr (&&) True (truncatable (show n))

truncatable :: [Char] -> [Bool]
truncatable n = map (myElem primes) (map h (delete "" (nub (inits n ++ tails n))))
  where h n = read n :: Int

main = print $ sum (take 11 $ filter g (drop 4 primes))

The truncatable function produces a list of boolean values indicating if all the numbers of a list are prime, while g performs the logical and over the list. Finally, the main function produces the result with the following execution time:

real 0m0.670s
user 0m0.662s
sys 0m0.006s
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: