0


私は知っています..タイトルはよく説明していません..
より良いタイトルがあればコメントで教えてください..
私は楽しみと学習の目的で素数ジェネレーターを作成しています..
ここに私のコードがあります:

divisors x xs = [ y | y <- [1]++xs++[x], x `mod` y == 0]
isPrime x xs = divisors x xs == [1,x]
primeLst = [ x | x <- [2..], isPrime x primeLst]

ご覧のとおり..実行時間を短縮するために新しい素数を生成するときに、既に生成された素数を条件で使用する必要があります..
それは機能していません..
それを作成する方法はありますか?

4

3 に答える 3

2

divisors関数を見てみましょう。それは、次の 2 つの問題だけで、ある程度は正しいです。

  1. xs主張はどうあるべきか？定義から、以下のすべての素数であるように見えますx- これらを素数候補と呼びましょう。xだった場合10、素数候補は になるはずです[2,3,5,7]。ただし、これは関数が引数として取得するものではありません。あなたのコードでxsは、素数の無限リストです。

  2. 技術的には、divisorsはすべての除数を返すわけではありません。たとえば、divisors 16 [2,3,5,7,11,13]は返されません。8しかし、これは些細な問題です。

divisorsしたがって、素数の正しいリストで呼び出すことができれば、問題はなく、isPrime関数も問題ありません。

問題は素数候補のリストを取得することです。わかりやすくするために、最初にコードを示し、次に説明します。

primeLst = 2 : [ x | x <- [3..], isPrime x (takeWhile (\p -> p*p <= x) primeLst)]

2 つの変更を加えました。

  1. primeLstが含まれていることを確認して2、前面に貼り付けました。

  2. 素数の無限リストから数を取得して、素数をテストしている数の平方根よりも大きい数に達するまで、素数の候補を制限しました。これを行う際に、素数候補の定義をわずかに変更したため、たとえば、 の候補26は[2,3,5]ではなく[2,3,5,7,11,13,17,19,23]. しかし、それでも機能します。

考えるべき 2 つの質問:

  1. 素数候補の新しい定義でも機能するのはなぜですか?

  2. 次のコード行は、素数候補の元の定義を提供する必要があるように見えますが、なぜ機能しないのでしょうか?

:

primeLst = 2 : [ x | x <- [3..], isPrime x (takeWhile (\p -> p < x) primeLst)]

最後の質問は難しいので、質問があればコメントに投稿してください。

于 2013-05-22T21:12:51.643 に答える
2 
dividedBy a b = a `mod` b == 0
isPrime x = null $ filter (x `dividedBy`) $ takeWhile (\y -> y * y <= x) primeLst
primeLst = 2:(filter isPrime [3..])

または、より詳細:

primeLst = 2:(filter isPrime [3..])
  where
    isPrime x = null $ primeDivisors x
    primeDivisors x = filter (x `dividedBy`) $ potentialDivisors x
    potentialDivisors x = takeWhile (\y -> y * y <= x) primeLst
    a `dividedBy` b = a `mod` b == 0
于 2013-05-22T21:13:25.410 に答える