题目

Problem 10: Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

第一个解答

两百万以下的素数的和是多少?使用 Haskell 解答如下:

isPrime n = null [ x | x <- [3,5..ceiling $ sqrt $ fromIntegral n], mod n x == 0 ]
main = print $ 2 + (sum $ takeWhile (<2*10^6) $ filter isPrime [3,5..])

这个程序的运行时间是 14.426 秒。

第二个解答

稍做改进后的 Haskell 程序:

small p (x:xs) = if p x then [] else x : small p xs
primes = 2:3:5:[ n | n <- [7,9..], all (\m -> 0 /= mod n m) $
  small (>ceiling(sqrt $ fromIntegral n)) primes ]
main = print $ sum $ takeWhile (<2*10^6) primes

这个程序的运行时间是 6.171 秒。

第三个解答

其实 Haskell 语言的函数库中有一个 primes 列表,可以直接使用:

import Math.NumberTheory.Primes.Sieve
main = print $ sum $ takeWhile (<2*10^6) primes

这个程序的运行时间是 0.146 秒。

以上三个程序均改写自“欧拉计划:007. 第10001个素数”,具体工作原理可参见该文。

参考资料

  1. Project Euler: 010_overview.pdf
  2. HaskellWiki: Prime numbers
  3. Hackage: arithmoi: Efficient basic number-theoretic functions. Primes, powers, integer logarithms.
  4. Haskell: Math.NumberTheory.Primes.Sieve
  5. LiteratePrograms: Sieve of Eratosthenes (Haskell)
  6. Wikipedia: Prime number theorem
  7. 图灵社区:欧拉计划:003. 最大素因子
  8. 图灵社区:欧拉计划:007. 第10001个素数