0

ここ数日、Learn You A Haskell を通じて Haskell を学んでいます。Project Euler の問題をいくつか解こうとしてきましたが、その中には素数が必要なものもあります。ただし、いくつか (この場合は 20000 未満の素数) を生成するために作成した関数は、正しく出力されません。実行すると、「[1、」GHCiが返され、一見終了しません。私が使用しているコードは次のとおりです。

sieve :: (Integral a) => a -> [a] -> [a]
sieve 20000 list = list
sieve n (x:xs) = sieve (n+1) $ x:(filter (\q -> q `mod` n /= 0) xs)

primesto20000 = sieve 2 [1..20000]

そして、私は電話してprimesto20000います。関数が非効率的である可能性があることを理解しています。主に、私が犯したに違いない構文/プロセスエラーについて助けを求めています.
ありがとうございました

4

2 に答える 2

2

コードには 2 つの問題があります。

  • その時間の複雑さ（私が推測する二次）のため、妥当な時間内に終了せず、ただハングしているように見えます。20000 を 200 に置き換えると終了しますが、結果は になります[1]。
  • もう 1 つの問題は、それぞれについて、 で割り切れるnすべての数値をフィルター処理することです。この条件を使用しないと、それ自体をフィルター処理することになり、すべての数値をフィルター処理することになります。nnn

修正されたバージョンは次のようになります (パラメータ化された制限付き):

limit :: Integral a => a
limit = 20000

sieve :: (Integral a) => a -> [a] -> [a]
sieve n list | n == limit
    = list
sieve n (x:xs)
    = sieve (n+1) $ x : (filter filt xs)
  where
    -- filter everything divisible by `n`, but not `n` itself.
    filt q = (q <= n) || (q `mod` n /= 0)

primesto20000 = sieve 2 [1..limit]
于 2013-02-05T09:13:48.520 に答える
2

素数だけでなく、すべての数の倍数を除外しています。xではなく、 で割り切れるかどうかを確認しnます。n（実際、sieve関数で必要かどうかはわかりません。primesto20000関数に適切な入力リストを生成させ、それを渡すだけです。）

于 2013-02-05T09:08:41.357 に答える