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

コードに2つのエラーがあります。最初は

Prelude Data.Char Main> truncatablePrime 3797
False

第二に、リスト内包条件が正しくありません。（それがあまりスポイラーではないことを願っています。）

于 2012-12-10T12:41:30.903 に答える