ソフィー・ジェルマン素数
30分プログラム、その166。CATVで見たプルーフ・オブ・マイ・ライフ [DVD]に登場したソフィー・ジェルマン素数を計算するプログラム。
ソフィー・ジェルマン素数は、2p+1が素数であるようなpのこと。例えば、2*2+1=5で2と5も素数なので、2はソフィー・ジェルマン素数。
こんな感じで登場した。
男「数学の世界は頭のおかしい男ばっかりだ」
女「女性もいるわよ。ソフィー・ジェルマンとか」
男「知らないなぁ。学会で会ったかもしれない」
女「ソフィー・ジェルマンは1776年、フランス生れよ」
男「それじゃあ会ったことないな」
男・女「・・・」
男「ジェルマン素数か!」
女「そう、2n+1」
男「2*2+1=5で2も5も素数」
女「2*1171+1=2343もそうよ」
使い方
*Main> head sophie 2 *Main> take 10 sophie [2,3,5,11,23,29,41,53,83,89]
ソースコード
sieve (x:xs) = x:sieve [y | y <- xs, y `mod` x /= 0] primes = sieve [2..] -- ソート済みリストでのみ使えるelem -- 無限リストにも適用可能 ordElem :: (Eq a,Ord a) => a -> [a] -> Bool ordElem x xs = x == (last $ fst $ break (> x) xs) -- ソフィー・ジェルマン素数(2p+1が素数であるようなp)の判定 -- e.g. 2*2+1=5で2と5も素数なので、2はソフィー・ジェルマン素数 -- 引数は素数とする isSophie :: Integer -> Bool isSophie p = let q = 2*p + 1 in ordElem q primes -- ソフィー・ジェルマン素数のリスト sophie = filter isSophie primes
