Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

訳

最初の六つの素数，2，3，5，7，11，13を列挙することで，6番目の素数が13であることがわかる．

10001番目の素数は何か．

[Haskell] 「エラトステネスの篩」と「6で割って余り1か5」

シンプルにエラトステネスの篩．スピードが遅いのは分かってます．

{-
e7.hs Project Euler Problem 7
エラトステネスの篩
-}
import System
primes=0:2:(eratos [3,5..])
    where eratos (p:ps) = p: (eratos [ x | x<-ps, x `mod` p /= 0 ])

main = getArgs >>= putStr.show.(primes!!).read.head

予想通り遅いです．
なお，答えは 104743 です．

そこで，「6で割って余り1か5」の戦略を使ってみます．素数の列を生成するタネとして，2:3:([6,12..]>>=(\x->[x-1,x+1))を使うのですが，6で割って余り1か5の数が，このリストの中の以下の値で割り切れる場合は素数ではないのです．したがって，そうではない数だけをリストに追加していけば，素数の列が得らます．

{-
e7-2.hs Project Euler Problem 7
6で割って余り1か5の数を素数の候補とするバージョン
-}
import System

primes::[Integer]
primes=2:3:([6,12..] >>= (\x ->(g (x-1))++(g (x+1))))

takeLeThanSqrt::Integer -> [Integer]-> [Integer]
takeLeThanSqrt y xs = takeWhile (\x -> leThanSqrt x y) xs

leThanSqrt::Integer -> Integer -> Bool
leThanSqrt x y = (fromInteger x) <= (sqrt $ fromInteger y )

g::Integer->[Integer]
g y 
    | [ x | x<-(takeLeThanSqrt y primes), y `mod` x ==0] == [] = [y]
    | otherwise = []


prime::Int -> Integer
prime n = primes!!(n-1)

main = getArgs >>= putStr.show.prime.read.head

大分速くなります．

hippo:~/haskell$ time ./e7 10001
104743
real    0m16.587s
user    0m15.505s
sys     0m0.256s
hippo:~/haskell$ time ./e7-2 10001
104743
real    0m0.331s
user    0m0.088s
sys     0m0.020s

ざっと50倍ですか．一桁増やして 100001 だと

hippo:~/haskell$ time ./e7-2 100001
1299721
real    0m8.333s
user    0m7.976s
sys     0m0.072s

となりました．エラトステネスの篩の方は怖くてやってません．