Primality by trial division: Difference between revisions
m
→Sieve by trial division
(→Sieve by trial division: rmv type signature ; promote "segmented generate-and-test"; copy-editing) |
|||
Line 478:
<lang haskell>primes = sieve [2..] where
sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]</lang>
As is shown in Melissa O'Neill's [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], this is rather a sub-optimal ''trial division'' algorithm. Its complexity is quadratic in number of primes produced whereas that of optimal trial division is <math>O(n^{1.5}/(\log n)^{0.5})</math>, and of true SoE it is <math>O(n\log n\log\log n)</math>, in ''n'' primes produced. It is easily fixed into having normal trial division complexity, by making it bounded again:
<lang haskell>primesTo m = 2 : sieve [3,5..m] where
Line 486 ⟶ 484:
| True = p : sieve [x | x <- xs, rem x p /= 0]</lang>
To make it unbounded, the guard can not be simply discarded.
===Segmented Generate and Test===
| |||