Primality by trial division: Difference between revisions

Content added Content deleted
Line 487: Line 487:


===Segmented Generate and Test===
===Segmented Generate and Test===
Starting each filter no sooner than it is actually needed, and rearranging to avoid recalculations, leads to this:
Explicating the list of filters on each segment between the consecutive squares of primes, as a list of factors to test by (so that no testing is done prematurely), and rearranging to avoid recalculations, leads to this:
<lang haskell>primes = 2 : 3 : sieve 5 9 (drop 2 primes) 0 where
<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
sieve x q ps k = let fs = take k (tail primes) in
Retrieved from "https://rosettacode.org/wiki/Primality_by_trial_division"