凤凰木的笔记 - 用 Haskell 实现一个求素数的算法

目的: 给定任意正整数 n, 返回不大于 n 的素数列表。算法要点: 递归地进行，对大于 n 平方根小于 n 的每一个数，都用不大于 n 平方根的素数去试除，筛出不能被除尽的所有数，然后和不大于 n 平方根内的素数列表合并。

module Main where
 
import System.Environment (getArgs)

primes :: Integer -> [Integer]
primes 1 = []
primes 2 = [2]
primes n = qs ++ [x | x <- [sqrtn..n], and [mod x y /= 0 | y <- qs]] where
  qs =  primes sqrtn
  sqrtn = floor $ sqrt $ fromInteger n + 1


main = do
  xs <- getArgs
  putStrLn . show . length . primes . read $ head xs

根据素数基本定理，此算法时间复杂度为 Ω(n*sqrt(n)/log(n)).

在 Macbook Air 上的 Linux 虚拟机跑一下看看:

weiwen@W11 ~/haskell/snippets % ghc prime.hs
[1 of 1] Compiling Main             ( prime.hs, prime.o )
Linking prime ...
weiwen@W11 ~/haskell/snippets % time ./prime 100
25
./prime 100  0.00s user 0.00s system 70% cpu 0.004 total
weiwen@W11 ~/haskell/snippets % time ./prime 1000
168
./prime 1000  0.00s user 0.01s system 93% cpu 0.005 total
weiwen@W11 ~/haskell/snippets % time ./prime 10000
1229
./prime 10000  0.01s user 0.00s system 96% cpu 0.012 total
weiwen@W11 ~/haskell/snippets % time ./prime 100000
9592
./prime 100000  0.07s user 0.00s system 99% cpu 0.078 total
weiwen@W11 ~/haskell/snippets % time ./prime 1000000
78498
./prime 1000000  1.26s user 0.01s system 99% cpu 1.269 total
weiwen@W11 ~/haskell/snippets % time ./prime 10000000
664579
./prime 10000000  28.35s user 0.16s system 99% cpu 28.510 total
weiwen@W11 ~/haskell/snippets % time ./prime 100000000
5761455
./prime 100000000  691.00s user 4.75s system 99% cpu 11:35.78 total