Haskellの素数

さて、1つinitは有限リストに対して何をするかを見てみましょう：

init [1] == []
init [1,2] == [1]
init [1,2,3] == [1,2]

わかりました。リストの最後の要素を除くすべてが表示されます。

それで、何init primesですか？さて、prime最後の要素なし。我々が実装されていればうまくいけば、prime正しくはないはず持っている（無限に多くの素数があるので！）最後の要素を、私たちは、とにかく今の完全なリストを持っていないので、もっと重要なのは、我々は非常にまだ気にする必要はありません-私たちだけ結局のところ、最初のいくつかの要素に注意を払うので、私たちにとってはそれprime自体とほとんど同じです。

さて、見てくださいall：これは何をしますか？それは、リストと述語を取り、リストのすべての要素が述語を満たしているかどうかを教えてくれます。

all (<5) [1..4] == True
all even [1..4] == False

無限のリストでも機能します！

all (<5) [1..] == False

では、ここで何が起こっているのでしょうか。さて、ここにあります：それは無限のリストで機能します...しかし、述語に違反するリストの最初の要素までリストを実際に評価できる場合に限ります！これがここに当てはまるかどうか見てみましょう：

all (\y -> (mod 5 y) > 0) (init prime)

したがって5、が素数であるかどうかを確認するには、素数からそれを分割する素数の最後の要素を引いた数があるかどうかを確認する必要があります。それができるかどうか見てみましょう。

素数の定義を見てみましょう。

all (\y -> (mod 5 y) > 0) (2:3:filter (\x -> all (\y -> (mod x y) > 0) (init prime)) [5..])

したがって、5が素数であるかどうかを判断するには、次のかどうかを確認するだけです。

1. 2で割り切れる-そうではない、続けましょう
2. 3で割り切れる-まだない
3. ...で割り切れる？さて、私たちは3番目の素数が何であるかをチェックしている最中なので、まだわかりません...

そして問題の核心があります。このロジックでは、3番目の素数を決定するには、3番目の素数を知る必要があります。もちろん、論理的には、実際にはこれをまったくチェックしたくありません。むしろ、小さい素数のいずれかが現在の候補の約数であるかどうかをチェックするだけで済みます。

では、どうすればそれを実現できるでしょうか。残念ながら、ロジックを変更する必要があります。私たちにできることの1つは、すでに持っている素数の数を覚えて、比較に必要な数だけ取るようにすることです。

prime = 2 : 3 : morePrimes 2 [5..]
  morePrimes n (x:xs)
    | all (\y -> mod x y > 0) (take n prime) = x : morePrimes (n+1) xs
    | otherwise                              = morePrimes n xs

では、これはどのように機能しますか？まあ、それは基本的に私たちは何について話したん：我々は、我々はすでにで始まる（持っているどのように多くの素数を覚えて2、我々は、少なくとも持って知っているので、[2,3]中にn私たちは、その後、私たちの次の素数は、のいずれかで割り切れるかどうかを確認します。n素数我々は既に知っていますを使用してtake n、それが次の素数であることがわかっているn場合は、インクリメントする必要があります。それ以外の場合は、続行します。

エラトステネスのふるいに触発された（まったく同じではありませんが）よりよく知られている形式もあります：

prime = sieve [2..] where
  sieve (p:xs) = p : sieve (filter (\x -> mod x p > 0) xs)

では、これはどのように機能しますか？さて、再び同様の考えで：次の素数は前の素数で割り切れない必要があることを私たちは知っています。どうしようか？さて、2リストの最初の要素が素数であることがわかります。次に、を使用して、その素数で割り切れるすべての数を破棄しfilterます。その後、リストの次の項目は再び素数になるので（破棄しなかったため）、プロセスを繰り返すことができます。

これらのどちらも、あなたが望んでいたようなワンライナーではありません。