project euler problem 7
Problem 7 †
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり、6番目の素数は 13 である。10001 番目の素数を求めよ。
再起で素数は難しいよ 値を引き回すのが面倒でしょうがない。
main = (putStrLn.show) problem problem = last $ primeList 10001 [2] nextPrime x xs = if not.or $ map ((==)0.(x`mod`)) xs then xs++[x] else nextPrime (x+1) xs primeList x xs = if length xs==x then xs else primeList x (nextPrime ((last xs)+1) xs)
ネット上で遅延評価で素数リストを得る方法発見 こんなの思いつかないorz
Prelude> let sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] in take 10 $ sieve [2..] [2,3,5,7,11,13,17,19,23,29] Prelude> let sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] in sieve [2..] !! 10 31 Prelude> let sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] in sieve [2..] !! 100 547 Prelude> let sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] in sieve [2..] !! 10001 104759