Project Euler No. 7

Problem

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

What is the 10,001st prime number?

Code in Haskell

Euler_007.hs

module Main where

--有名だが凄まじく非効率的

--primes = 2:(sieve [3,5..])
--sieve (x:xs) = x:(sieve [ a | a<-xs, mod a x /= 0])


--Richard BirdによるSieve of Eratosthenes

primes = 2:(section [3..] composites)
  where
    composites = union [multiples p |p<-primes]
    multiples n = map (n*) [n..]

section (x:xs) (y:ys)
  | x < y = x : (section xs (y:ys))
  | x == y = section xs ys
  | x > y = section (x:xs) ys 

union = foldr merge []
  where
    merge (x:xs) ys = x:merge' xs ys
    merge' (x:xs) (y:ys)
      | x < y = x : merge' xs (y:ys)
      | x == y = x : merge' xs ys
      | x > y = y : merge' (x:xs) ys

main = print answer
  where answer = primes!!10000

Answer

1****3

Comments

有名なsieveの1行コードは恐ろしく非効率的である、ということも今回初めて知ったという安定の情弱ぶりである。この古典的な1行コードをボコっている、Melissa O'Neilによる、sieveはlist構造ではなくpriority queueで実現しろ（大意）、という論文は勉強になりました。Priority Queueとか初めて知った情弱です。リストがどうしても時間的に不利なのはしょうがないよね。コードにあるのは、O'Neilの論文に掲載されていた、Richard Bird大先生による「エラトステネスの篩」をあくまでリストで実現したもの（論文ではお前らみんなリストが好き過ぎ、と軽くdisられている）。

まとめ：Data.Numbers.Primes パッケージから素数の無限リスト(Primes)と素数性述語(isPrime)使え。