Anonymous user
Primality by trial division: Difference between revisions
m
→Sieve by trial division
m (→compact version: made version 1 similar to version 2 (SAY instructions). -- ~~~~) |
|||
Line 586:
Bounded formulation has normal trial division complexity, because it can stop early through an explicit guard:
<lang haskell>primesTo m = 2 : sieve [3,5..m] where
sieve (p:xs) | p*p > m = p : xs
|
====Postponed sieve by trial division====
To make it unbounded, the guard cannot be simply discarded, the firing up of a filter by a prime should be ''postponed'' until its ''square'' is seen amongst the candidates:
<lang haskell>primesT = 2 : 3 : sieve [5,7..] 9 (tail primesT) where
sieve (x:xs) q ps@(p:t) | x < q = x : sieve xs q ps
|
====Segmented Generate and Test====
| |||