素数ってどうやるんだっけ?
思い出しながら、100までの素数のリストを計算してみました。
primes :: Int -> [Int]
primes 2 = [ 2 ]
primes n = primes (n - 1) ++ isPrime n
where
isPrime :: Int -> [Int]
isPrime 3 = [ 3 ]
isPrime n
| even n = [ ]
| notPrime n = [ ]
| otherwise = [ n ]
notPrime :: Int -> Bool
notPrime n =
elem 0 . map (mod n ) . tail . primes . floor . sqrt . fromIntegral $ n
main = print $ primes 100
実行結果
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
primesは素数のリスト。
nを素数かどうか判定して、n-1までのリストと結合します。
isPrimeは素数判定。
n が 偶数か、素数でないものなら [ ] 、
そうでなければ [ n ] を返します。
notPrimeは素数でないかどうか。
奇数 n の平方根以下の素数(2を除く)で割って、割り切れたらTrue、そうでなければFalse。
2で割る、というのが偶数判定とかぶるので tailで取りました。
primesからもisPrimeを呼んでるし、isPrimeからもprimesを呼んでるしで何かエラー出たら面倒だなと思ってたんだけど、何ごともなく動いてちょっと感動。
あるかないかわからないものを簡単に足すために ++ を使ってみました。
でも足す中味が一個なのでちょっとおもしろくないかな?
もっといい方法があればご教示ください。
##追記
コメントで教えていただいた記事を勉強してみましたメモ。
99 Haskell Problems より、[31] でもその前に
Haskell で「素数列」をつくる。
最新(修正)版を引用。
primes.hs
--
-- 素数列（修正版）
--
-- http://d.hatena.ne.jp/notogawa/20110114/1295006865 を参考に
-- gcd の使い方が秀逸
--
primes :: Integral a => [a]
primes = map fromIntegral $ [2, 3] ++ primes'
where
primes' = [5] ++ f 1 7 primes'
f m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) ps
where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]
まだ全貌は理解できていませんが、わかったことなど。
有限でなく、無限リスト
小さい方から、ちょっとずつ(なにかの二乗まで?)計算して,さらにその先を再帰的に追加している。
###効率よく
6n+1とか、ん?と思ったが、なるほど。
要するに、あらかじめ 2 と 3 の倍数を除いたリストを直接、生成している。
すべての素数で割ってみるのと、すべての素数をかけたものと最大公約数をとってみるのと同じ。
しかもコストが安い。