Primality by trial division: Difference between revisions
→Sieve by trial division: rmv type signature ; promote "segmented generate-and-test"; copy-editing
m (→Sieve by trial division: whitespace (uniformity)) |
(→Sieve by trial division: rmv type signature ; promote "segmented generate-and-test"; copy-editing) |
||
Line 476:
===Sieve by trial division===
One often sees a ''"naive"'' version presented as an unbounded [[Sieve of Eratosthenes#Haskell|sieve of Eratosthenes]], similar to David Turner's 1975 SASL code,
<lang haskell>primes
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
The above is easily fixed into having normal trial division complexity,
<lang haskell>primesTo m = 2 : sieve [3,5..m] where
Line 489 ⟶ 488:
To make it unbounded, the guard can not be simply discarded.
Starting each filter no sooner than it is actually needed, and rearranging to avoid
<lang haskell>primes = 2 : 3 : sieve 5 9 (drop 2 primes) 0 where
sieve x q ps k = let fs = take k (tail primes) in
Line 496 ⟶ 495:
++ sieve (q+2) (head ps^2) (tail ps) (k+1)</lang>
=={{header|HicEst}}==
| |||