Primality by trial division: Difference between revisions
revert my wrong edit, add comments
(→Segmented Generate and Test: comment, for clarity) |
(revert my wrong edit, add comments) |
||
Line 1,071:
primesST = 2 : 3 : sieve 5 9 (drop 2 primesST) (inits $ tail primesST) where
sieve x q ps (fs:ft) = filter (
++ sieve (q+2) (head ps^2) (tail ps) ft</lang>
<code>inits</code> makes a stream of (progressively growing) prefixes of an input stream, starting with an empty prefix
Runs at empirical <math>O(n^{1.4...})</math> time complexity, in ''n'' primes produced. Can be used as a framework for unbounded segmented sieves, replacing divisibility testing with proper sieve of Eratosthenes on arrays, etc.
The filtering function is equivalent to <code>noDivsBy</code> [[#Haskell|defined above]], except that the comparisons with the square root are no longer needed and so are spared.
=={{header|HicEst}}==
| |||