Sequence of primes by trial division: Difference between revisions
Sequence of primes by trial division (view source)
Revision as of 19:48, 28 January 2015
, 9 years ago→{{header|Haskell}}: consistent names for functions, whitespace
(→Sieve by trial division: use the original indentation in code) |
(→{{header|Haskell}}: consistent names for functions, whitespace) |
||
Line 177:
===Sieve by trial division===
Filtering candidate numbers for non-divisibility, by prime at a time, is a kind of sieving. One often sees a ''"naive"'' version presented as an unbounded [[Sieve of Eratosthenes#Haskell|sieve of Eratosthenes]], similar to David Turner's 1975 SASL code,
<lang haskell>
where
sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]
-- map head
-- . iterate (\(p:xs)-> [x | x <- xs, rem x p /= 0]) $ [2..]</lang>
Line 186:
===Bounded sieve by trial division===
Bounded formulation has normal trial division complexity, because it can stop early via an explicit guard:
<lang haskell>primesTo m = 2 : sieve [3,5..m]
where
sieve (p:xs) | p*p > m = p : xs
| otherwise = p : sieve [x | x <- xs, rem x p /= 0]
Line 194 ⟶ 195:
===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 (so a bigger chunk of input numbers are taken straight away as primes, between each opening up of a new filter, instead of just one head element in the non-postponed algorithm):
<lang haskell>
where
sieve (x:xs) q ps@(p:t) | x < q = x : sieve xs q ps -- inlined (span (< q))▼
sieve (x:xs) q ps@(p:t)
| otherwise = sieve [y | y <- xs, rem y p /= 0] (head t^2) t▼
-- ps = concat . map fst
--
--
===Segmented Generate and Test===
Line 205 ⟶ 208:
<lang haskell>import Data.List (inits)
primesST = 2 : 3 : sieve 5 9 (drop 2 primesST) (inits $ tail primesST)
where
sieve x q ps (fs:ft) = filter (\y-> all ((/=0).rem y) fs) [x,x+2..q-2]
++ sieve (q+2) (head ps^2) (tail ps) ft</lang>
| |||