Primality by trial division: Difference between revisions
Content added Content deleted
(→Segmented Generate and Test: code tweak - about 10% slower cmpld, x4 faster interp'd in GHCi) |
(→Segmented Generate and Test: correct cpxty) |
||
| Line 493: | Line 493: | ||
++ sieve (q+2) (head ps^2) (tail ps) (k+1)</lang> |
++ sieve (q+2) (head ps^2) (tail ps) (k+1)</lang> |
||
Runs at empirical <math>O(n^{1. |
Runs at empirical <math>O(n^{1.41})</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 etc. |
||
=={{header|HicEst}}== |
=={{header|HicEst}}== |
||