Project Euler Problem 7
http://projecteuler.net/index.php?section=problems&id=7
10001番目の素数を求める。
nextPrime,isPrimeはProblem3から
--時間かかりすぎ main = print $ ((primeList 1) !! 10000) primeList :: Integer -> [Integer] primeList n = [nextPrime n] ++ (primeList $ nextPrime n) nextPrime :: Integer -> Integer nextPrime n = head $ filter (\n -> isPrime n) [n+1..] isPrime :: Integer -> Bool isPrime 1 = False isPrime n = null [x | x <- [2..n-1], n `mod` x == 0]
素数を求めるプログラムを参考に修正
main = print $ ((primeList 1) !! 10000) primeList :: Integer -> [Integer] primeList n = let x = nextPrime n in [x] ++ (primeList x) --2以外の素数は奇数だけチェック nextPrime :: Integer -> Integer nextPrime n = if n < 2 then 2 else head $ filter (\n -> isPrime n) [x | x <- [n+1..], odd x] --約数チェックは平方根未満まででおk isPrime :: Integer -> Bool isPrime 1 = False isPrime n = null [x | x <- [2..floor $ sqrt $ fromInteger n], n `mod` x == 0]