Primality by trial division: Difference between revisions
→{{header|Haskell}}: rmv the 1st, inefficient version ; code tweak ; move here sieve by TD from SoE page
(→{{header|Haskell}}: rmv the 1st, inefficient version ; code tweak ; move here sieve by TD from SoE page) |
|||
Line 460:
=={{header|Haskell}}==
<lang haskell>
-- primeNums = filter (coprime [2..]) [2..]
▲primeQ primes n = n > 1 && foldr (\p r-> p*p>n || (rem n p /= 0 && r)) True primes
primeNums = 2 : 3 : filter (coprime $ tail primeNums) [5,7..]</lang>
Any increasing ''unbounded'' primes source
▲Any ''unbounded'' primes source (as well as, less efficiently, ''odds'' prefixed with 2) can be used with the testing function <code>primeQ</code> to define <code>isPrime</code>, say one from [[Sieve of Eratosthenes#Haskell|Sieve of Eratosthenes]], or <code>primeQ</code> itself can be used to define primes list corecursively as e.g. <code>primeNums</code> above, because it stops as soon as the square root is reached.
Trial division can be used to quickly produce short ranges of primes:
<lang haskell>primesFromTo n m =
===Sieve by trial division===
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>primes :: [Integer]
primes = sieve [2..] where
sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]</lang>
As is shown in Melissa O'Neill's [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], this is rather a sub-optimal ''trial division'' algorithm. Its complexity is quadratic in number of primes produced whereas that of optimal trial division is <math>O(n^{1.5}/(\log n)^{0.5})</math>, and of true SoE it is <math>O(n\log n\log\log n)</math>, in ''n'' primes produced. A priority queue-based SoE version also is presented in the article, with and without [http://en.wikipedia.org/wiki/Wheel_factorization wheels].
The above is easily fixed into having normal trial division complexity, at a price of making it bounded again:
<lang haskell>primesTo m = 2 : sieve [3,5..m] where
sieve (p:xs) | p*p > m = p : xs
| True = p : sieve [x | x<-xs, rem x p /= 0]</lang>
To make it unbounded, the guard can not be simply discarded.
====Segmented Generate and Test====
Starting each filter no sooner than it is actually needed, and rearranging to avoid redundant recalculations, leads to the following.
<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
[n | n <- [x,x+2..q-2], and [rem n f /= 0 | f <- fs]]
++ sieve (q+2) (head ps^2) (tail ps) (k+1)</lang>
Can be used as a framework for unbounded segmented sieves, replacing divisibility testing with e.g. proper SoE code on arrays etc. Runs at empirical <math>O(n^{1.45})</math> time complexity, in ''n'' primes produced.
▲The code for <code>primeNums</code>, when inlined, rearranged and optimized, leads to segmented "generate-and-test" [[Sieve_of_Eratosthenes#Segmented Generate and Test|sieve by trial division]].
=={{header|HicEst}}==
| |||