CODEWITHSUNDEEP
haskelloptimizationprimes
chrisbuchholz
chrisbuchholz

Reputation: 639

Project Euler #37: my solution is too slow

I am toying with project euler problem 37. The problem is stated as follows:

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

This is my code:

import Data.Char

prime n
    | n < 2                                                                       = False
    | n == 2                                                                      = True
    | length [x | x <- [2..(floor . sqrt $ fromIntegral n)], n `mod` x == 0] == 0 = True
    | otherwise                                                                   = False

truncateList xs = take (length xs) $ iterate init xs

truncateSteps n = truncateList nn ++ truncateList rn
            where
                nn = map digitToInt $ show n
                rn = reverse nn

truncatablePrime n = and $ map (\ns -> prime $ foldl (\x y -> 10 * x + y) 0 ns) $ truncateSteps n

main = print $ sum $ take 11 $ [n | n <- [9,11..], notElem 5 $ map digitToInt $ show n, truncatablePrime n]

I believe that my code will yield the correct result if it would finish. It is simply all too slow. I have optimized a few things, like not counting numbers that contain the digit '5' and only checking for 'primeness' up to the square root of the number, but it is not enough at all.

I would like some hints to other optimizations I could look into. Now, keep in mind that I am a new acquantance of haskell, but do suggest anything you think is worth a mention.

UPDATE This is the finished solution which runs in just about 1 second on my machine: https://gist.github.com/4250615

Thanks for all the optimization-pointers!

Upvotes: 1

Views: 809

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183978

You have two errors in your code, first

Prelude Data.Char Main> truncatablePrime 3797
False

and second, your list comprehension conditions are not correct. (Hope that isn't too much of a spoiler.)

Upvotes: 1

Related Questions