1

我在玩项目欧拉问题37。问题说明如下：

数字 3797 有一个有趣的特性。作为素数本身，可以从左到右连续删除数字，并在每个阶段保持素数：3797、797、97 和 7。类似地，我们可以从右到左工作：3797、379、37 和 3。

求从左到右和从右到左都可截断的仅有的 11 个素数之和。

注意：2、3、5 和 7 不被视为可截断的素数。

这是我的代码：

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]

我相信如果我的代码完成，它会产生正确的结果。简直太慢了。我已经优化了一些东西，比如不计算包含数字“5”的数字，只检查“素数”直到数字的平方根，但这还不够。

我想对我可以研究的其他优化提供一些提示。现在，请记住，我是 haskell 的新朋友，但请提出您认为值得一提的任何建议。

更新 这是完成的解决方案，在我的机器上运行大约 1 秒：https ://gist.github.com/4250615

感谢所有优化指针！

4

1 回答 1

1

您的代码中有两个错误，首先

Prelude Data.Char Main> truncatablePrime 3797
False

其次，您的列表理解条件不正确。（希望这不是太多的剧透。）

于 2012-12-10T12:41:30.903 回答