素数判定(試し割り)

gistfile1.hs

isPrime :: Int -> Bool
isPrime 1 = False
-- 約数リストを作成し、それが1,xのみである(それ以外の約数リストがnull)かどうかを判定して返却
--
-- lazy evaluation(怠惰な評価)で、最初の約数がリストに入れられた時点で
-- null評価されFalseを返すことを期待しているが、そうなのか？
--
isPrime x = null [f| f<-[2..x-1], 0 == mod x f]


-- 実際には、「1の次の約数はxではない」ことを示すにはsqrt xまでを走査すれば十分
isPrime' :: Int -> Bool
isPrime' 1 = False
isPrime' x = null [f| f<-[2..s], 0 == mod x f]
    where s = truncate (sqrt (fromIntegral x))  -- 平方根を丸め込むためにここまでしないといけない？


-- 再帰を用いた実装
isPrime'' :: Int -> Bool
isPrime'' 1 = False
isPrime'' x =
    let s = (sqrt . fromIntegral) x;
        findFactorGreaterThan | s < fromIntegral f = False | 0 == mod x f = True | otherwise = findFactorGreaterThan (f+1)
    in not $ findFactorGreaterThan 2
 

-- isPrime'よりもちょっとだけ遅い。。ような気がする。ベンチマークとかどうやってとるんや
isPrime''' :: Int -> Bool
isPrime''' 1 = False
isPrime''' x = 0 == length [f| f<-[2..s], 0 == mod x f]
    where s = (truncate . sqrt . fromIntegral) x -- 関数合成による記法


isPrime'''' :: Int -> Bool
isPrime'''' 1 = False
-- 高階関数+関数合成で書き直し。余計見づらい
isPrime'''' x = null $ filter ((== 0) . (mod x)) [2..s]
-- lambdaのほうがマシか
-- isPrime'''' x = null $ filter (\f -> 0 == mod x f) [2..s]
    where s = (truncate . sqrt . fromIntegral) x