它非常慢，因为该算法是一种试除法，不会停止于平方根。
如果你仔细观察算法的作用，你会发现对于每个素数p，其不具有较小素因数的倍数将从候选列表中删除（具有较小素因数的倍数之前已被删除）。
因此，每个数字都除以所有素数，直到它作为其最小素因数的倍数被删除，或者如果它是素数，则它出现在剩余候选列表的开头。
对于合数来说，这并不是特别糟糕，因为大多数合数都有小的素因数，并且在最坏的情况下，最小的素因数n不超过√n.
But the primes are divided by all smaller primes, so until the kth prime is found to be prime, it has been divided by all k-1 smaller primes. If there are m primes below the limit n, the work needed to find all of them prime is
(1-1) + (2-1) + (3-1) + ... + (m-1) = m*(m-1)/2
部门。由素数定理 http://en.wikipedia.org/wiki/Prime_number_theorem，下面的素数个数n是渐进的n / log n (where log表示自然对数）。消除复合材料的工作可以粗略地限制为n * √n划分，所以不能太小n与花在素数上的工作相比，这是可以忽略不计的。
For the primes to two million, the Turner sieve needs roughly 1010 divisions. Additionally, it needs to deconstruct and reconstruct a lot of list cells.
试除法止于平方根，
isPrime n = go 2
where
go d
| d*d > n = True
| n `rem` d == 0 = False
| otherwise = go (d+1)
primes = filter isPrime [2 .. ]
would need fewer than 1.9*109 divisions (brutal estimate if every isPrime n check went to √n - actually, it takes only 179492732 because composites are generally cheap)(1) and much fewer list operations. Additionally, this trial division is easily improvable by skipping even numbers (except 2) as candidate divisors, which halves the number of required divisions.
埃拉托色尼筛不需要任何划分，只使用O(n * log (log n))操作，速度要快得多：
primeSum.hs:
module Main (main) where
import System.Environment (getArgs)
import Math.NumberTheory.Primes
main :: IO ()
main = do
args <- getArgs
let lim = case args of
(a:_) -> read a
_ -> 1000000
print . sum $ takeWhile (<= lim) primes
并以 1000 万的限制运行它：
$ ghc -O2 primeSum && time ./primeSum 10000000
[1 of 1] Compiling Main ( primeSum.hs, primeSum.o )
Linking primeSum ...
3203324994356
real 0m0.085s
user 0m0.084s
sys 0m0.000s
我们让试除法只运行到 100 万（将类型固定为Int):
$ ghc -O2 tdprimeSum && time ./tdprimeSum 1000000
[1 of 1] Compiling Main ( tdprimeSum.hs, tdprimeSum.o )
Linking tdprimeSum ...
37550402023
real 0m0.768s
user 0m0.765s
sys 0m0.002s
而特纳筛只能到100000：
$ ghc -O2 tuprimeSum && time ./tuprimeSum 100000
[1 of 1] Compiling Main ( tuprimeSum.hs, tuprimeSum.o )
Linking tuprimeSum ...
454396537
real 0m2.712s
user 0m2.703s
sys 0m0.005s
(1) The brutal estimate is
2000000
∑ √k ≈ 4/3*√2*10^9
k = 1
评估为两位有效数字。由于大多数数字都是由一个小质因数组成的复合数 - 一半的数字是偶数并且只进行一次除法 - 这大大高估了所需的除法数量。
仅考虑素数即可获得所需除法数量的下限：
∑ √p ≈ 2/3*N^1.5/log N
p < N
p prime
which, for N = 2000000 gives roughly 1.3*108. That is the right order of magnitude, but underestimates by a nontrivial factor (decreasing slowly to 1 for growing N, and never greater than 2 for N > 10).
除了素数之外，素数的平方和两个相近素数的乘积也需要试除达到（接近）√k因此，如果数量足够多的话，将对整体工作做出重大贡献。
然而，处理半素数所需的除法次数受到常数倍数的限制
N^1.5/(log N)^2
所以对于非常大的N相对于处理素数的成本来说，它可以忽略不计。但在试分割完全可行的范围内，它们仍然做出了重大贡献。
