社員ブログ
HOME  社員ブログ

アーカイブ

‘Haskell’ カテゴリ

【Haskell勉強中】素数判定

2013年01月4日 13時08分38秒

こんにちは、年末から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とか超ダサいですし、できれば関数をひとつにまとめたいですけど、そのへんはおいおい。


Haskell, 社員:ピーター