Skip to content

Instantly share code, notes, and snippets.

@honda0510
Last active December 10, 2015 15:09
Show Gist options
  • Save honda0510/4452658 to your computer and use it in GitHub Desktop.
Save honda0510/4452658 to your computer and use it in GitHub Desktop.
【Haskell】素数判定
-- 試し割り
isPrime :: Int -> Bool
isPrime 2 = True
isPrime n
| n < 2 = False
| (n `mod` 2) == 0 = False
| otherwise = testDiv 3 n
where testDiv :: Int -> Int -> Bool
testDiv i n
| i * i > n = True
| n `mod` i == 0 = False
| otherwise = testDiv (i + 2) n
-- エラトステネスのふるい
isPrime' :: Int -> Bool
isPrime' n
| n < 2 = False
| otherwise = n == last (sieveOfE [2..n])
-- Sieve of Eratosthenes
where sieveOfE :: [Int] -> [Int]
sieveOfE [] = []
sieveOfE [a] = [a]
sieveOfE all@(x:xs)
| x < 2 = error "`head list` must be `> 1`"
| last xs < x ^ 2 = all
| otherwise = x : sieveOfE [n | n <- all, n `mod` x /= 0]
@cmddot
Copy link

cmddot commented Jan 9, 2013

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment