単純な素数判定 - mrsekut-p

単純な素数判定

最も単純なもの

1~nまで割り続ければ良い

code:hs

isPrime :: Integer -> Bool

isPrime n

| n < 2 = False

| otherwise = all (\i -> n mod i /= 0) 2..n-1

単純な工夫で試行回数を減らす

code:hs

isPrime :: Integer -> Bool

isPrime n

| n < 2 = False

| n == 2 = True

| even n = False -- ①

| otherwise = all (\i -> n mod i /= 0) 2..isqrt n -- ②

where

isqrt = floor . sqrt . fromIntegral

①

2以上の偶数なら素数ではない

試行回数が半分減る

②

$ 2\sim Nではなく$ 2\sim\sqrt{N}で十分

例えば、$ N=18の時、約数のペアは以下の通り

(1,18)

(2,9)

(3,6)

ペアの小さい方は必ず$ \sqrt{18}以下になる