Primality by trial division: Difference between revisions
Content added Content deleted
m (→Infinite list of primes: Rewritten a bit) |
(→Segmented Generate and Test: use function that's already there) |
||
| Line 1,071: | Line 1,071: | ||
primesST = 2 : 3 : sieve 5 9 (drop 2 primesST) (inits $ tail primesST) where |
primesST = 2 : 3 : sieve 5 9 (drop 2 primesST) (inits $ tail primesST) where |
||
sieve x q ps (fs:ft) = filter ( |
sieve x q ps (fs:ft) = filter (noDivsBy fs) [x,x+2..q-2] |
||
++ sieve (q+2) (head ps^2) (tail ps) ft</lang> |
++ 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. |
<code>inits</code> makes a stream of (progressively growing) prefixes of an input stream, starting with an empty prefix. <code>noDivsBy</code> is [[#Haskell|defined above]]. |
||
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. |
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. |
||