Primality by trial division: Difference between revisions
Content added Content deleted
(→Sieve by trial division: rmv type signature ; promote "segmented generate-and-test"; copy-editing) |
|||
Line 478: | Line 478: | ||
<lang haskell>primes = sieve [2..] where |
<lang haskell>primes = sieve [2..] where |
||
sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]</lang> |
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. |
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: |
||
The above is easily fixed into having normal trial division complexity, by making it bounded again: |
|||
<lang haskell>primesTo m = 2 : sieve [3,5..m] where |
<lang haskell>primesTo m = 2 : sieve [3,5..m] where |
||
Line 486: | Line 484: | ||
| True = p : sieve [x | x <- xs, rem x p /= 0]</lang> |
| True = p : sieve [x | x <- xs, rem x p /= 0]</lang> |
||
To make it unbounded, the guard can not be simply discarded. |
To make it unbounded, the guard can not be simply discarded. |
||
===Segmented Generate and Test=== |
===Segmented Generate and Test=== |