Primality by trial division: Difference between revisions
Content added Content deleted
(→Sieve by trial division: c/e) |
|||
| Line 581: | Line 581: | ||
sieve (p:xs) | p*p > m = p : xs |
sieve (p:xs) | p*p > m = p : xs |
||
| True = p : sieve [x | x <- xs, rem x p /= 0]</lang> |
| True = p : sieve [x | x <- xs, rem x p /= 0]</lang> |
||
To make it unbounded, the guard cannot be simply discarded. |
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. |
||
===Segmented Generate and Test=== |
===Segmented Generate and Test=== |
||
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: |
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: |
||