素数判定、素数の数え上げ、素数関数

• Haskellのリストと集合内包表現(だけ)を使って素数判定、自然数の増加と疎の自然数までの素数の数の増加についての関数を作る
• ある自然数が素数であるかどうかの判定をその数より１より小さい自然数までのすべてで割った余りが０でないかどうかを判定するより、その自然数までの素数で割った余りが…とする方が処理は速そうだが、ひとまず、その工夫はしないでおこう

-- Haskell の集合の内包表現を使って
-- 次の手順で素数に関する処理をしてみる
-- myprime
-- まず2以上の自然数xを与え、[2..x-1]で割った余りが0になる個数を返す関数
let myprime x = (length ([y | y <- [2.. x-1], x `mod` y==0]) )
-- myprime2
-- myprime2の値が0であることが素数の判断条件なのでその真偽値を返す関数
let myprime2 x = ((myprime x) == 0)
-- myprime3
-- 2以上の自然数xを与え、[2 .. x]について、myprime2関数が真を返すことを条件に
-- 自然数x以下の素数を列挙する関数
let myprime3 x = [y | y <- [2 .. x], (myprime2 y)]
-- myprime4
-- 2以上の自然数x以下の素数の数を返す関数
myprime4 x = length ( myprime3 x)
-- myprime5
-- 2以上の自然数xを与え、[2 .. x]について、それぞれの自然数以下の素数の数を返す関数
-- この素数の数がどのように増えるかは、「リーマン予想」と関係する関数
let myprime5 x = [myprime4 y | y <- [2 ..x]]

-- 実行結果
Prelude> myprime 12
4
Prelude> myprime2 12
False
Prelude> myprime2 13
True
Prelude> myprime3 12
[2,3,5,7,11]
Prelude> myprime4 12
5
Prelude> myprime5 12
[1,2,2,3,3,4,4,4,4,5,5]