Tweet

こんにちは、年末から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, 社員：ピーター