【Haskell勉強中】素数判定
こんにちは、年末からHaskellを勉強しているピーターです。
知り合いから、「暇だったらどうぞ → ある数xが素数かどうか判定する関数 isPrime x = ??」と問題が出されましたのでやってみました。
C言語による素数判定(試し割り)のプログラム例をHaskellで書き直しました。
C
int IsPrime(int n){ int i; if(n < 2) return 0; else if(n == 2) return 1; if(n % 2 == 0) return 0; for(i = 3; i * i <= n; i += 2) if(n % i == 0) return 0; return 1; }
Haskell
isPrime :: Int -> Bool isPrime 2 = True isPrime n | n < 2 = False | (n `mod` 2) == 0 = False | otherwise = wari 3 n wari :: Int -> Int -> Bool wari i n = if i * i <= n then (if n `mod` i == 0 then False else wari (i + 2) n) else True
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
作成したisPrime関数をテストしてみます。
*Main> [n | n <- [1..100], isPrime n] [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]
できているようです。
wariとか超ダサいですし、できれば関数をひとつにまとめたいですけど、そのへんはおいおい。
最近のコメント