# Prime numbers

(Difference between revisions)
 Revision as of 23:43, 11 February 2012 (edit) (typo)← Previous diff Revision as of 11:02, 25 January 2013 (edit) (undo)m (→Tree merging: minor c/e)Next diff → (42 intermediate revisions not shown.) Line 1: Line 1: - In mathematics, ''amongst the natural numbers greater than 1'', a ''prime number'' (or a ''prime'') is such that has no divisors other than itself (and 1). The smallest prime is thus 2. Non-prime numbers are known as ''composite'', i.e. those representable as product of two natural numbers greater than 1. The set of prime numbers is thus '''P''' = '''N'''2 \ {''n''×''m'' : ''n'',''m'' ∈ '''N'''2} = '''N'''2 \ ∪ { {''n''×''n'',''n''×''n''+''n'',''n''×''n''+2×''n'', ...}: ''n'' ∈ '''N'''2 }, where '''N'''k = {''n'' ∈ '''N''': ''n'' ≥ k}. + In mathematics, ''amongst the natural numbers greater than 1'', a ''prime number'' (or a ''prime'') is such that has no divisors other than itself (and 1). - + - Thus starting with 2, for each newly found prime we can ''eliminate'' from the rest of the numbers ''all the multiples'' of this prime, giving us the next available number as next prime. This is known as ''sieving'' the natural numbers, so that in the end all the composites are eliminated and what we are left with are just primes. + - + - To eliminate a prime's multiples we can either '''a.''' test each new candidate number for divisibility by that prime, giving rise to a kind of ''trial division'' algorithm; or '''b.''' we can directly generate the multiples of a prime ''p'' by counting up from it in increments of ''p'', resulting in a variant of the ''sieve of Eratosthenes''. + - + - Having a direct-access mutable arrays indeed enables easy marking off of these multiples on pre-allocated array as it is usually done in imperative languages; but to get an [[#Tree merging with Wheel|efficient ''list''-based code]] we have to be smart about combining those streams of multiples of each prime - which gives us also the memory efficiency in generating the results incrementally, one by one. + == Prime Number Resources == == Prime Number Resources == Line 21: Line 15: * Papers: * Papers: ** O'Neill, Melissa E., [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004. ** O'Neill, Melissa E., [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004. + + == Definition == + + In mathematics, ''amongst the natural numbers greater than 1'', a ''prime number'' (or a ''prime'') is such that has no divisors other than itself (and 1). The smallest prime is thus 2. Non-prime numbers are known as ''composite'', i.e. those representable as product of two natural numbers greater than 1. The set of prime numbers is thus + + : '''P''' = {''n'' ∈ '''N'''2 ''':''' (∀ ''m'' ∈ '''N'''2) ((''m'' | ''n'') ⇒ m = n)} + + :: = {''n'' ∈ '''N'''2 ''':''' (∀ ''m'' ∈ '''N'''2) (''m''×''m'' ≤ ''n'' ⇒ ¬(''m'' | ''n''))} + + :: = '''N'''2 \ {''n''×''m'' ''':''' ''n'',''m'' ∈ '''N'''2} = + + :: = '''N'''2 \ '''∪''' { {''n''×''m'' ''':''' ''m'' ∈ '''N'''n} ''':''' ''n'' ∈ '''N'''2 } + + :: = '''N'''2 \ '''∪''' { {''n''×''n'', ''n''×''n''+''n'', ''n''×''n''+2×''n'', ...} ''':''' ''n'' ∈ '''N'''2 } + + :: = '''N'''2 \ '''∪''' { {''n''×''n'', ''n''×''n''+''n'', ''n''×''n''+2×''n'', ...} ''':''' ''n'' ∈ '''P''' }          where   '''N'''k = {''n'' ∈ '''N''' ''':''' ''n'' ≥ k}. + + Thus starting with 2, for each newly found prime we can ''eliminate'' from the rest of the numbers ''all the multiples'' of this prime, giving us the next available number as next prime. This is known as ''sieving'' the natural numbers, so that in the end all the composites are eliminated and what we are left with are just primes. (This is what the last formula is describing, though seemingly [http://en.wikipedia.org/wiki/Impredicativity impredicative], because it is self-referential. But because '''N'''2 is well-ordered (with the order being preserved under addition), the formula is well-defined.) + + To eliminate a prime's multiples we can either '''a.''' test each new candidate number for divisibility by that prime, giving rise to a kind of ''trial division'' algorithm; or '''b.''' we can directly generate the multiples of a prime ''p'' by counting up from it in increments of ''p'', resulting in a variant of the ''sieve of Eratosthenes''. + + Having a direct-access mutable arrays indeed enables easy marking off of these multiples on pre-allocated array as it is usually done in imperative languages; but to get an [[#Tree merging with Wheel|efficient ''list''-based code]] we have to be smart about combining those streams of multiples of each prime - which gives us also the memory efficiency in generating the results incrementally, one by one. == Sieve of Eratosthenes == == Sieve of Eratosthenes == + + The sieve of Eratosthenes calculates primes as natural numbers above 1 without the composites, where composites are found as sequences of multiples of each prime, generated by counting up from the prime's square in constant increments equal to that prime (or twice that much, for odd primes): + + + primes = 2 : 3 : ([5,7..] minus unionAll [[p*p, p*p+2*p..] | p <- tail primes]) + + + unionAll can be defined as an ever-growing, right-deepening unbounded [[#Tree_merging|tree of comparisons]] like the joinT function below, or it can use a (fixed-sized) array as a segment-wise sorting and duplicates-removing device, to join together the streams of multiples of primes. The processing naturally divides up into segments between the successive squares of primes. + + Stepwise development follows (the fully developed version is [[#Tree merging with Wheel|here]]). + + === Initial definition === + To start with, the sieve of Eratosthenes can be genuinely represented by To start with, the sieve of Eratosthenes can be genuinely represented by Line 29: Line 58: eratos [] = [] eratos [] = [] eratos (p:xs) = p : eratos (xs minus [p, p+2*p..m]) eratos (p:xs) = p : eratos (xs minus [p, p+2*p..m]) - -- eulers (p:xs) = p : eulers (xs minus map (p*)(p:xs)) -- will be dealt + -- eulers (p:xs) = p : eulers (xs minus map (p*)(p:xs)) - -- turner (p:xs) = p : turner [x | x <- xs, rem x p /= 0] -- with later on + -- turner (p:xs) = p : turner [x | x <- xs, rem x p /= 0] - This should be regarded more like a ''specification'', not a code (the fully developed version is [[#Tree merging with Wheel|here]]). It is extremely slow, running at empirical time complexities worse than quadratic in number of primes produced. But it has the core defining features of the classical formulation of S. of E. as '''''a.''''' being bounded, i.e. having a top limit value, and '''''b.''''' finding out the multiples of a prime directly, by counting up from it, in increments of the prime's value (or twice that, to count on odds only). + This should be regarded more like a ''specification'', not a code. It is extremely slow, running at empirical time complexities worse than quadratic in number of primes produced. But it has the core defining features of the classical formulation of S. of E. as '''''a.''''' being bounded, i.e. having a top limit value, and '''''b.''''' finding out the multiples of a prime directly, by counting up from it in increments equal to that prime (or twice that, for odd primes). - The canonical list-difference minus and duplicates-removing list-union union functions dealing with ordered increasing lists - infinite as well as finite - are simple enough to define (cf. Leon P.Smith's [http://hackage.haskell.org/packages/archive/data-ordlist/0.4.4/doc/html/Data-List-Ordered.html Data.List.Ordered] package): + The canonical list-difference minus and duplicates-removing list-union union functions dealing with ordered increasing lists - infinite as well as finite - are simple enough to define (cf. Leon P.Smith's [http://hackage.haskell.org/packages/archive/data-ordlist/latest/doc/html/Data-List-Ordered.html Data.List.Ordered] package): -- ordered lists, difference and union -- ordered lists, difference and union Line 90: Line 119: So while minus(a,b) takes $O(|b|)$ operations for random-access imperative arrays and about $O(|a|)$ operations for lists here, using Haskell's immutable array for ''a'' one ''could'' expect the array update time to be nevertheless closer to $O(|b|)$ if destructive update were used implicitly by compiler for an array being passed along as an accumulating parameter: So while minus(a,b) takes $O(|b|)$ operations for random-access imperative arrays and about $O(|a|)$ operations for lists here, using Haskell's immutable array for ''a'' one ''could'' expect the array update time to be nevertheless closer to $O(|b|)$ if destructive update were used implicitly by compiler for an array being passed along as an accumulating parameter: + {-# OPTIONS_GHC -O2 #-} import Data.Array.Unboxed import Data.Array.Unboxed - primesToA m = sieve 3 (array (3,m) [(i,odd i) | i<-[3..m]] :: UArray Int Bool) + primesToA m = sieve 3 (array (3,m) [(i,odd i) | i<-[3..m]] + :: UArray Int Bool) where where sieve p a sieve p a Line 100: Line 131: - This indeed seems to be working with the type signature added explicitly (suggested by Daniel Fischer), the above code running relatively very fast, with empirical complexity of about $O(n^{1.35})$ in ''n'' primes produced. But it relies on compiler traits, and indeed if we remove the explicit type signature, the code above turns very slow. + This indeed seems to be working for unboxed arrays, with the type signature added explicitly (suggested by Daniel Fischer), the above code running relatively '''very fast''', with empirical complexity of about '''$O(n^{1.15..1.45})$''' in ''n'' primes produced (for producing from few hundred thousands to few millions primes, memory usage also slowly growing). But it relies on specific compiler optimizations, and indeed if we remove the explicit type signature, the code above turns ''very'' slow. - How can we write code that we'd be certain about? One way is to use explicitly mutable monadic arrays (''see below''), but we can also think about it a little bit more on the functional side of things. + How can we write code that we'd be certain about? One way is to use explicitly mutable monadic arrays ([[#Using Mutable Arrays|''see below'']]), but we can also think about it a little bit more on the functional side of things still. === Postponed === === Postponed === Line 155: Line 186: But segmentation doesn't add anything substantially, and each multiples stream starts at its prime's square anyway. What does the [[#Postponed|Postponed]] code do, operationally? For each prime's square passed over, it builds up a nested linear ''left-deepening'' structure, '''''(...((xs-a)-b)-...)''''', where '''''xs''''' is the original odds-producing ''[3,5..]'' list, so that each odd it produces must go through more and more minus nodes on its way up - and those odd numbers that eventually emerge on top are prime. Thinking a bit about it, wouldn't another, ''right-deepening'' structure, '''''(xs-(a+(b+...)))''''', be better? This idea is due to Richard Bird (in the code presented in Melissa O'Neill's article). But segmentation doesn't add anything substantially, and each multiples stream starts at its prime's square anyway. What does the [[#Postponed|Postponed]] code do, operationally? For each prime's square passed over, it builds up a nested linear ''left-deepening'' structure, '''''(...((xs-a)-b)-...)''''', where '''''xs''''' is the original odds-producing ''[3,5..]'' list, so that each odd it produces must go through more and more minus nodes on its way up - and those odd numbers that eventually emerge on top are prime. Thinking a bit about it, wouldn't another, ''right-deepening'' structure, '''''(xs-(a+(b+...)))''''', be better? This idea is due to Richard Bird (in the code presented in Melissa O'Neill's article). - Here, ''xs'' would stay near the top, and ''more frequently'' odds-producing streams of multiples of ''smaller'' primes would be above those of the ''bigger'' primes, that produce ''less frequently'' their candidates which have to pass through ''more'' union nodes on their way up. Plus, no explicit synchronization is necessary anymore because the produced multiples of a prime start at its square anyway - just some care has to be taken to avoid a runaway access to the infinitely-defined structure (specifically, if each (+) operation passes along unconditionally its left child's head value ''before'' polling the right child's head value, then we are safe). + + primesLME1 = 2 : primes' + where + primes' = 3 : ([5,7..] minus joinL [[p*p, p*p+2*p..] | p <- primes']) + joinL ((x:xs):t) = x : union xs (joinL t) + + + Here, ''xs'' stays near the top, and ''more frequently'' odds-producing streams of multiples of ''smaller'' primes are above those of the ''bigger'' primes, that produce ''less frequently'' their candidates which have to pass through ''more'' union nodes on their way up. Plus, no explicit synchronization is necessary anymore because the produced multiples of a prime start at its square anyway - just some care has to be taken to avoid a runaway access to the indefinitely-defined structure (specifically, if each (+)/union operation passes along unconditionally its left child's head value ''before'' polling the right child's head value, then we are safe). - Here's the code, faster yet but still with same time complexity of about $O(n^{1.4})$: + To prevent unneeded memoization and thus prevent a memory leak, double primes feed can be introduced as per Melissa O'Neill's code. Here's the code, faster yet but still with the same empirical orders of growth of about ~ $n^{1.4}$: primesLME = 2 : ([3,5..] minus joinL [[p*p, p*p+2*p..] | p <- primes']) primesLME = 2 : ([3,5..] minus joinL [[p*p, p*p+2*p..] | p <- primes']) where where - primes' = 3 : ([5,7..] minus joinL [[p*p, p*p+2*p..] | p <- primes']) + primes' = 3 : ([5,7..] minus joinL [[p*p, p*p+2*p..] | p <- primes']) joinL ((x:xs):t) = x : union xs (joinL t) joinL ((x:xs):t) = x : union xs (joinL t) - The double primes feed is introduced here to prevent unneeded memoization and thus prevent memory leak, as per Melissa O'Neill's code. + This allows the primesLME stream to be discarded immediately as it is being consumed by its consumer. With primes' it is impossible, as each produced member of primes' is needed later as input to the same primes' stream definition. So the primes' stream feeds in a loop to itself, and thus is retained in memory; and it is also used as input stream for the main stream production, but it reaches only up to a square root of where the main stream, primesLME, reaches, as its production is demanded by its consumer(s). === Tree merging === === Tree merging === Line 173: Line 211: - primesTME = 2 : (gaps 3 $joinT [[p*p, p*p+2*p..] | p <- primes']) + primesTME = 2 : gaps 3 (joinT [[p*p, p*p+2*p..] | p <- primes']) where where - primes' = 3 : (gaps 5$ joinT [[p*p, p*p+2*p..] | p <- primes']) + primes' = 3 : gaps 5 (joinT [[p*p, p*p+2*p..] | p <- primes']) joinT ((x:xs):t) = x : union xs (joinT (pairs t)) joinT ((x:xs):t) = x : union xs (joinT (pairs t)) Line 185: Line 223: It is [http://ideone.com/p0e81 very fast], running at speeds and empirical complexities comparable with the code from Melissa O'Neill's article (about $O(n^{1.2})$ in number of primes ''n'' produced). It is [http://ideone.com/p0e81 very fast], running at speeds and empirical complexities comparable with the code from Melissa O'Neill's article (about $O(n^{1.2})$ in number of primes ''n'' produced). - As an aside, joinT is equivalent to calling [[Fold#Tree-like_folds|infinite tree-like folding]] foldi (\(x:xs) ys->x:union xs ys) []. + As an aside, joinT is equivalent to [[Fold#Tree-like_folds|infinite tree-like folding]] foldi (\(x:xs) ys->x:union xs ys) []. The above can be [http://ideone.com/qpnqe rewritten] as follows, using a standard (corecursive) definition for fix combinator from Data.Function to arrange for double primes feed automatically: The above can be [http://ideone.com/qpnqe rewritten] as follows, using a standard (corecursive) definition for fix combinator from Data.Function to arrange for double primes feed automatically: - + import Data.Function (fix) + primesTMEf = 2 : g (fix g) primesTMEf = 2 : g (fix g) where where g xs = 3 : gaps 5 (joinT [[x*x, x*x+2*x..] | x <- xs]) g xs = 3 : gaps 5 (joinT [[x*x, x*x+2*x..] | x <- xs]) - fix g = xs where xs = g xs -- global defn to avoid space leak + -- fix g = xs where xs = g xs Line 220: Line 259: ====Above Limit - Offset Sieve==== ====Above Limit - Offset Sieve==== - Another task is to produce primes above a given value (i.e. not from their ordinal numbers). + Another task is to produce primes above a given value (i.e. not by their ordinal numbers): {-# OPTIONS_GHC -O2 -fno-cse #-} {-# OPTIONS_GHC -O2 -fno-cse #-} - primesFromTMWE primes m = (if m <= 2 then [2] else []) + primesFromTMWE primes m = dropWhile (< m) [2,3,5,7,11] - ++ (gapsW a wh' $compositesFrom a) + ++ gapsW a wh' (compositesFrom a) where where - (a,wh') = rollFrom (snap (max 3 m) 3 2) + (a,wh') = rollFrom (snapUp (max 3 m) 3 2) (h,p':t) = span (< z)$ drop 4 primes -- p < z => p*p<=a (h,p':t) = span (< z) $drop 4 primes -- p < z => p*p<=a z = ceiling$ sqrt $fromIntegral a + 1 -- p'>=z => p'*p'>a z = ceiling$ sqrt $fromIntegral a + 1 -- p'>=z => p'*p'>a - snap v origin step = if r==0 then v else v+(step-r) - where r = mod (v-origin) step compositesFrom a = joinT (joinST [multsOf p a | p <- h++[p']] compositesFrom a = joinT (joinST [multsOf p a | p <- h++[p']] : [multsOf p (p*p) | p <- t]) : [multsOf p (p*p) | p <- t]) - multsOf p from = scanl (\c d->c+p*d) (p*x) wh -- map (p*)$ - where -- scanl (+) x wh - (x,wh) = rollFrom (snap from p (2*p) div p) - wheelNums = scanl (+) 0 wheel + snapUp v o step = v + ((o-v) mod step) -- full steps from o - rollFrom n = go wheelNums wheel + multsOf p from = scanl (\c d->c+p*d) (p*x) wh -- map (p*) $- where m = (n-11) mod 210 + where -- scanl (+) x wh - go (x:xs) ws@(w:ws') | x < m = go xs ws' + (x,wh) = rollFrom (snapUp from p (2*p) div p) -- , if p < from - | True = (n+x-m, ws) -- (x >= m) + wheelNums = scanl (+) 0 wheel + rollFrom n = go wheelNums wheel + where m = (n-11) mod 210 + go (x:xs) ws@(w:ws') | x < m = go xs ws' + | True = (n+x-m, ws) -- (x >= m) Line 248: Line 286: primesFrom m = filter isPrime [m..] primesFrom m = filter isPrime [m..] + + + === Map-based === + Runs ~1.7x slower than [[#Tree_merging|TME version]], but with the same empirical time complexity, ~$n^{1.2}$ (in ''n'' primes produced) and same very low (near constant) memory consumption: + + + import Data.List -- based on http://stackoverflow.com/a/1140100 + import qualified Data.Map as M + + primesMPE :: [Integer] + primesMPE = 2:mkPrimes 3 M.empty prs 9 -- postponed addition of primes into map; + where -- decoupled primes loop feed + prs = 3:mkPrimes 5 M.empty prs 9 + mkPrimes n m ps@ ~(p:t) q = case (M.null m, M.findMin m) of + (False, (n', skips)) | n == n' -> + mkPrimes (n+2) (addSkips n (M.deleteMin m) skips) ps q + _ -> if n Line 289: Line 349: The above is equivalent to the traditional formulation of trial division, The above is equivalent to the traditional formulation of trial division, - noDivs factors n = foldr (\f r -> f*f > n || (rem n f /= 0 && r)) True factors + noDivs factors n = foldr (\f r -> f*f > n || (rem n f /= 0 && r)) + True factors -- primes = filter (noDivs [2..]) [2..] -- primes = filter (noDivs [2..]) [2..] primesTD = 2 : 3 : filter (noDivs$ tail primesTD) [5,7..] primesTD = 2 : 3 : filter (noDivs $tail primesTD) [5,7..] Line 338: Line 399: - primesEU = 2 : euler [3,5..] where + primesEU = 2 : eulers [3,5..] where - euler (p:xs) = p : euler (xs minus map (p*) (p:xs)) + eulers (p:xs) = p : eulers (xs minus map (p*) (p:xs)) + -- eratos (p:xs) = p : eratos (xs minus [p*p, p*p+2*p..]) - This code is extremely inefficient, running above $O({n^{2}})$ complexity (and worsening rapidly), and should be regarded a ''specification'' only. Its memory usage is very high, with space complexity just below $O({n^{2}})$, in ''n'' primes produced. + This code is extremely inefficient, running above $O({n^{2}})$ empirical complexity (and worsening rapidly), and should be regarded a ''specification'' only. Its memory usage is very high, with empirical space complexity just below $O({n^{2}})$, in ''n'' primes produced. + + In the stream-based sieve of Eratosthenes we are able to ''skip'' along the input stream xs directly to the prime's square, consuming the whole prefix at once, thus achieving the results equivalent to the postponement technique, because the generation of the prime's multiples is independent of the rest of the stream. + + But here in the Euler's sieve it ''is'' dependent on all xs and we're unable ''in principle'' to skip along it to the prime's square - because all xs are needed for each prime's multiples generation. Thus efficient unbounded stream-based implementation seems to be impossible in principle, under the simple scheme of producing the multiples by multiplication. === Wheeled list representation === === Wheeled list representation === Line 394: Line 460: === Generating Segments of Primes === === Generating Segments of Primes === - The removal of multiples on each segment of odds can be done by actually marking them in an array instead of manipulating the ordered lists, and can be further sped up more than twice by working with odds only, represented as their offsets in segment arrays: + The sieve of Eratosthenes'es [[#Segmented|removal of multiples on each segment of odds]] can be done by actually marking them in an array instead of manipulating the ordered lists, and can be further sped up more than twice by working with odds only, represented as their offsets in segment arrays: Line 418: Line 484: === Calculating Primes Upto a Given Value === === Calculating Primes Upto a Given Value === + + Equivalent to [[#Accumulating Array|Accumulating Array]] above, running somewhat faster (compiled by GHC with optimizations turned on): + {-# OPTIONS_GHC -O2 #-} + import Data.Array.Unboxed + primesToNA n = 2: [i | i <- [3,5..n], ar ! i] primesToNA n = 2: [i | i <- [3,5..n], ar ! i] where where Line 427: Line 498: | True = if null x then a' else f (head x) a' | True = if null x then a' else f (head x) a' where q = p*p where q = p*p + a' :: UArray Int Bool a'= a // [(i,False) | i <- [q, q+2*p..n]] a'= a // [(i,False) | i <- [q, q+2*p..n]] x = [i | i <- [p+2,p+4..n], a' ! i] x = [i | i <- [p+2,p+4..n], a' ! i] Line 438: Line 510: where where o = max (if even a then a+1 else a) 3 o = max (if even a then a+1 else a) 3 - r = floor.sqrt.fromInteger$ b+1 + r = floor . sqrt $fromIntegral b + 1 ar = accumArray (\a b-> False) True (o,b) ar = accumArray (\a b-> False) True (o,b) [(i,()) | p <- [3,5..r] [(i,()) | p <- [3,5..r] Line 561: Line 633: * [[Testing_primality#Primality_Test_and_Integer_Factorization | Primality Test and Integer Factorization ]] * [[Testing_primality#Primality_Test_and_Integer_Factorization | Primality Test and Integer Factorization ]] * [[Testing_primality#Miller-Rabin_Primality_Test | Miller-Rabin Primality Test]] * [[Testing_primality#Miller-Rabin_Primality_Test | Miller-Rabin Primality Test]] + + == One-liners == + See [[Prime_numbers_miscellaneous#One-liners | primes one-liners]]. == External links == == External links == * http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip * http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip : A collection of prime generators; the file "ONeillPrimes.hs" contains one of the fastest pure-Haskell prime generators; code by Melissa O'Neill. : A collection of prime generators; the file "ONeillPrimes.hs" contains one of the fastest pure-Haskell prime generators; code by Melissa O'Neill. - : WARNING: Don't use the priority queue from older versions of that file for your projects: it's broken and works for primes only by a lucky chance. The revised version of the file fixes the bug, as pointed out by Eugene Kirpichov on February 24, 2009 on the [http://www.mail-archive.com/haskell-cafe@haskell.org/msg54618.html haskell-cafe] mailing list, and fixed by Bertram Felgenhauer. + : WARNING: Don't use the priority queue from ''older versions'' of that file for your projects: it's broken and works for primes only by a lucky chance. The ''revised'' version of the file fixes the bug, as pointed out by Eugene Kirpichov on February 24, 2009 on the [http://www.mail-archive.com/haskell-cafe@haskell.org/msg54618.html haskell-cafe] mailing list, and fixed by Bertram Felgenhauer. * [http://ideone.com/willness/primes test entries] for (some of) the above code variants. * [http://ideone.com/willness/primes test entries] for (some of) the above code variants. ## Revision as of 11:02, 25 January 2013 In mathematics, amongst the natural numbers greater than 1, a prime number (or a prime) is such that has no divisors other than itself (and 1). ## Contents ## 1 Prime Number Resources • At Wikipedia: • HackageDB packages: • arithmoi: Various basic number theoretic functions; efficient array-based sieves, Montgomery curve factorization ... • Numbers: An assortment of number theoretic functions. • NumberSieves: Number Theoretic Sieves: primes, factorization, and Euler's Totient. • primes: Efficient, purely functional generation of prime numbers. • Papers: • O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004. ## 2 Definition In mathematics, amongst the natural numbers greater than 1, a prime number (or a prime) is such that has no divisors other than itself (and 1). The smallest prime is thus 2. Non-prime numbers are known as composite, i.e. those representable as product of two natural numbers greater than 1. The set of prime numbers is thus P = {nN2 : (∀ mN2) ((m | n) ⇒ m = n)} = {nN2 : (∀ mN2) (m×mn ⇒ ¬(m | n))} = N2 \ {n×m : n,mN2} = = N2 \ { {n×m : mNn} : nN2 } = N2 \ { {n×n, n×n+n, n×n+2×n, ...} : nN2 } = N2 \ { {n×n, n×n+n, n×n+2×n, ...} : nP } where Nk = {nN : n ≥ k}. Thus starting with 2, for each newly found prime we can eliminate from the rest of the numbers all the multiples of this prime, giving us the next available number as next prime. This is known as sieving the natural numbers, so that in the end all the composites are eliminated and what we are left with are just primes. (This is what the last formula is describing, though seemingly impredicative, because it is self-referential. But because N2 is well-ordered (with the order being preserved under addition), the formula is well-defined.) To eliminate a prime's multiples we can either a. test each new candidate number for divisibility by that prime, giving rise to a kind of trial division algorithm; or b. we can directly generate the multiples of a prime p by counting up from it in increments of p, resulting in a variant of the sieve of Eratosthenes. Having a direct-access mutable arrays indeed enables easy marking off of these multiples on pre-allocated array as it is usually done in imperative languages; but to get an efficient list-based code we have to be smart about combining those streams of multiples of each prime - which gives us also the memory efficiency in generating the results incrementally, one by one. ## 3 Sieve of Eratosthenes The sieve of Eratosthenes calculates primes as natural numbers above 1 without the composites, where composites are found as sequences of multiples of each prime, generated by counting up from the prime's square in constant increments equal to that prime (or twice that much, for odd primes): primes = 2 : 3 : ([5,7..] minus unionAll [[p*p, p*p+2*p..] | p <- tail primes]) unionAll can be defined as an ever-growing, right-deepening unbounded tree of comparisons like the joinT function below, or it can use a (fixed-sized) array as a segment-wise sorting and duplicates-removing device, to join together the streams of multiples of primes. The processing naturally divides up into segments between the successive squares of primes. Stepwise development follows (the fully developed version is here). ### 3.1 Initial definition To start with, the sieve of Eratosthenes can be genuinely represented by -- genuine yet wasteful sieve of Eratosthenes primesTo m = 2 : eratos [3,5..m] where eratos [] = [] eratos (p:xs) = p : eratos (xs minus [p, p+2*p..m]) -- eulers (p:xs) = p : eulers (xs minus map (p*)(p:xs)) -- turner (p:xs) = p : turner [x | x <- xs, rem x p /= 0] This should be regarded more like a specification, not a code. It is extremely slow, running at empirical time complexities worse than quadratic in number of primes produced. But it has the core defining features of the classical formulation of S. of E. as a. being bounded, i.e. having a top limit value, and b. finding out the multiples of a prime directly, by counting up from it in increments equal to that prime (or twice that, for odd primes). The canonical list-difference minus and duplicates-removing list-union union functions dealing with ordered increasing lists - infinite as well as finite - are simple enough to define (cf. Leon P.Smith's Data.List.Ordered package): -- ordered lists, difference and union minus (x:xs) (y:ys) = case (compare x y) of LT -> x : minus xs (y:ys) EQ -> minus xs ys GT -> minus (x:xs) ys minus xs _ = xs union (x:xs) (y:ys) = case (compare x y) of LT -> x : union xs (y:ys) EQ -> x : union xs ys GT -> y : union (x:xs) ys union xs [] = xs union [] ys = ys The name merge ought to be reserved for duplicates-preserving merging operation of mergesort. ### 3.2 Analysis So for each newly found prime the sieve removes its odd multiples from further consideration. It finds them by counting up in steps of 2p. There are thus O(m / p) multiples generated and eliminated for each prime, and O(mloglog(m)) multiples in total, with duplicates, by virtues of prime harmonic series. If each multiple is dealt with in O(1) time, this will translate into O(mloglog(m)) RAM machine operations (since we consider addition as an atomic operation). Indeed mutable random-access arrays allow for that. But lists in Haskell are sequential-access, and complexity of minus(a,b) for lists is $\textstyle O(|a \cup b|)$ instead of $\textstyle O(|b|)$ of the direct access destructive array update. The lower the complexity of each minus step, the better the overall complexity. So on k-th step the argument list (p:xs) that the eratos function gets starts with the (k+1)-th prime, and consists of all the numbers ≤ m coprime with all the primes ≤ p. According to the M. O'Neill's article (p.10) there are $\textstyle\Phi(m,p) \in \Theta(m/\log p)$ such numbers. It looks like $\textstyle\sum_{i=1}^{n}{1/log(p_i)} = O(n/\log n)$ for our intents and purposes. Since the number of primes below m is n = π(m) = O(m / log(m)) by the prime number theorem (where π(m) is a prime counting function), there will be n multiples-removing steps in the algorithm; it means total complexity of at least O(mn / log(n)) = O(m2 / (log(m))2), or O(n2) in n primes produced - much much worse than the optimal O(nlog(n)loglog(n)). ### 3.3 From Squares But we can start each step at a prime's square, as its smaller multiples will have been already produced on previous steps. This means we can stop early, when the prime's square reaches the top value m, and thus cut the total number of steps to around $\textstyle n = \pi(m^{0.5}) = \Theta(2m^{0.5}/\log m)$. This does not in fact change the complexity of random-access code, but for lists it makes it O(m1.5 / (logm)2), or O(n1.5 / (logn)0.5) in n primes produced, a dramatic speedup: primesToQ m = 2 : sieve [3,5..m] where sieve [] = [] sieve (p:xs) = p : sieve (xs minus [p*p, p*p+2*p..m]) Its empirical complexity is about O(n1.45). This simple optimization works here because our formulation is bounded, as is the original algorithm. To start late on a bounded sequence is to stop early (if we start past its end we don't need to start at all – see warning below), thus preventing the creation of all the superfluous multiples streams which started above the upper bound anyway. This is acceptably slow now, striking a good balance between clarity, succinctness and efficiency. Warning: this is predicated on a subtle point of minus xs [] = xs definition being used, as it indeed should be. If the definition minus (x:xs) [] = x:minus xs [] is used, the problem is back and the complexity is bad again. ### 3.4 Guarded This ought to be explicated (improving on clarity, though not on time complexity) as in the following, for which it is indeed a minor optimization whether to start from p or p*p - because it explicitly stops as soon as possible: primesToG m = 2 : sieve [3,5..m] where sieve (p:xs) | p*p > m = p : xs | otherwise = p : sieve (xs minus [p*p, p*p+2*p..]) It is now clear that it can't be made unbounded just by abolishing the upper bound m, because the guard can not be simply omitted without changing the complexity back for the worst. ### 3.5 Accumulating Array So while minus(a,b) takes O( | b | ) operations for random-access imperative arrays and about O( | a | ) operations for lists here, using Haskell's immutable array for a one could expect the array update time to be nevertheless closer to O( | b | ) if destructive update were used implicitly by compiler for an array being passed along as an accumulating parameter: {-# OPTIONS_GHC -O2 #-} import Data.Array.Unboxed primesToA m = sieve 3 (array (3,m) [(i,odd i) | i<-[3..m]] :: UArray Int Bool) where sieve p a | p*p > m = 2 : [i | (i,True) <- assocs a] | a!p = sieve (p+2)$ a//[(i,False) | i <- [p*p, p*p+2*p..m]]
| otherwise = sieve (p+2) a

This indeed seems to be working for unboxed arrays, with the type signature added explicitly (suggested by Daniel Fischer), the above code running relatively very fast, with empirical complexity of about O(n1.15..1.45) in n primes produced (for producing from few hundred thousands to few millions primes, memory usage also slowly growing). But it relies on specific compiler optimizations, and indeed if we remove the explicit type signature, the code above turns very slow.

How can we write code that we'd be certain about? One way is to use explicitly mutable monadic arrays (see below), but we can also think about it a little bit more on the functional side of things still.

### 3.6 Postponed

Going back to guarded Eratosthenes, first we notice that though it works with minimal number of prime multiples streams, it still starts working with each a bit prematurely. Fixing this with explicit synchronization won't change complexity but will speed it up some more:

primesPE = 2 : primes'
where
primes' = sieve [3,5..] 9 primes'
sieve (x:xs) q ps@ ~(p:t)
| x < q     = x : sieve xs q ps
| otherwise =     sieve (xs minus [q, q+2*p..]) (head t^2) t

Since the removal of a prime's multiples here starts at the right moment, and not just from the right place, the code could now finally be made unbounded. Because no multiples-removal process is started prematurely, there are no extraneous multiples streams, which were the reason for the extreme wastefulness and thus inefficiency of the original formulation.

### 3.7 Segmented

With work done segment-wise between the successive squares of primes it becomes

primesSE = 2 : primes'
where
primes' = sieve 3 9 primes' []
sieve x q ~(p:t) fs =
foldr (flip minus) [x,x+2..q-2]
[[y+s, y+2*s..q] | (s,y) <- fs]
++ sieve (q+2) (head t^2) t
((2*p,q):[(s,q-rem (q-y) s) | (s,y) <- fs])

This "marks" the odd composites in a given range by generating them - just as a person performing the original sieve of Eratosthenes would do, counting one by one the multiples of the relevant primes. These composites are independently generated so some will be generated multiple times.

The advantage to working in spans explicitly is that this code is easily amendable to using arrays for the composites marking and removal on each finite span; and memory usage can be kept in check by using fixed sized segments.

#### 3.7.1 Segmented Tree-merging

Rearranging the chain of subtractions into a subtraction of merged streams (see below) and using tree-like folding structure, further speeds up the code and significantly improves its asymptotic time behavior (down to about O(n1.28empirically), space is leaking though):

primesSTE = 2 : primes'
where
primes' = sieve 3 9 primes' []
sieve x q ~(p:t) fs =
([x,x+2..q-2] minus joinST [[y+s, y+2*s..q] | (s,y) <- fs])
++ sieve (q+2) (head t^2) t
((++ [(2*p,q)]) [(s,q-rem (q-y) s) | (s,y) <- fs])

joinST (x:xs) = union x (joinST (pairs xs)) where
pairs (x:y:xs) = union x y : pairs xs
pairs xs       = xs
joinST []     = []

### 3.8 Linear merging

But segmentation doesn't add anything substantially, and each multiples stream starts at its prime's square anyway. What does the Postponed code do, operationally? For each prime's square passed over, it builds up a nested linear left-deepening structure, (...((xs-a)-b)-...), where xs is the original odds-producing [3,5..] list, so that each odd it produces must go through more and more minus nodes on its way up - and those odd numbers that eventually emerge on top are prime. Thinking a bit about it, wouldn't another, right-deepening structure, (xs-(a+(b+...))), be better? This idea is due to Richard Bird (in the code presented in Melissa O'Neill's article).

primesLME1 = 2 : primes'
where
primes' = 3 : ([5,7..] minus joinL [[p*p, p*p+2*p..] | p <- primes'])
joinL ((x:xs):t) = x : union xs (joinL t)

Here, xs stays near the top, and more frequently odds-producing streams of multiples of smaller primes are above those of the bigger primes, that produce less frequently their candidates which have to pass through more union nodes on their way up. Plus, no explicit synchronization is necessary anymore because the produced multiples of a prime start at its square anyway - just some care has to be taken to avoid a runaway access to the indefinitely-defined structure (specifically, if each (+)/union operation passes along unconditionally its left child's head value before polling the right child's head value, then we are safe).

To prevent unneeded memoization and thus prevent a memory leak, double primes feed can be introduced as per Melissa O'Neill's code. Here's the code, faster yet but still with the same empirical orders of growth of about ~ n1.4:

primesLME = 2 : ([3,5..] minus joinL [[p*p, p*p+2*p..] | p <- primes'])
where
primes' = 3 : ([5,7..] minus joinL [[p*p, p*p+2*p..] | p <- primes'])

joinL ((x:xs):t) = x : union xs (joinL t)

This allows the primesLME stream to be discarded immediately as it is being consumed by its consumer. With primes' it is impossible, as each produced member of primes' is needed later as input to the same primes' stream definition. So the primes' stream feeds in a loop to itself, and thus is retained in memory; and it is also used as input stream for the main stream production, but it reaches only up to a square root of where the main stream, primesLME, reaches, as its production is demanded by its consumer(s).

### 3.9 Tree merging

Moreover, it can be changed into a tree structure. This idea is due to Dave Bayer on haskell-cafe mailing list (though in much more complex formulation):

primesTME = 2 : gaps 3 (joinT [[p*p, p*p+2*p..] | p <- primes'])
where
primes' = 3 : gaps 5 (joinT [[p*p, p*p+2*p..] | p <- primes'])

joinT ((x:xs):t) = x : union xs (joinT (pairs t))
pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t
gaps k s@(x:xs) | k<x  = k:gaps (k+2) s    -- equivalent to
| True =   gaps (k+2) xs   --  [k,k+2..]minuss, k<=head s

It is very fast, running at speeds and empirical complexities comparable with the code from Melissa O'Neill's article (about O(n1.2) in number of primes n produced).

As an aside, joinT is equivalent to infinite tree-like folding foldi (\(x:xs) ys->x:union xs ys) [].

The above can be rewritten as follows, using a standard (corecursive) definition for fix combinator from Data.Function to arrange for double primes feed automatically:

import Data.Function (fix)

primesTMEf = 2 : g (fix g)
where
g xs = 3 : gaps 5 (joinT [[x*x, x*x+2*x..] | x <- xs])

-- fix g = xs where xs = g xs

### 3.10 Tree merging with Wheel

Wheel factorization optimization can be further applied, and another tree structure can be used which is better adjusted for the primes multiples production (effecting about 5%-10% at the top of a total 2.5x speedup w.r.t. the above tree merging on odds only - though complexity stays roughly the same):

{-# OPTIONS_GHC -O2 -fno-cse #-}
primesTMWE = 2:3:5:7: gapsW 11 wheel (joinT3 $rollW 11 wheel primes') where primes' = 11: gapsW 13 (tail wheel) (joinT3$ rollW 11 wheel primes')

gapsW k ws@(w:t) cs@(c:u) | k==c  = gapsW (k+w) t u
| True  = k : gapsW (k+w) t cs
rollW k ws@(w:t) ps@(p:u) | k==p  = scanl (\c d->c+p*d) (p*p) ws
: rollW (k+w) t u
| True  = rollW (k+w) t ps
joinT3 ((x:xs): ~(ys:zs:t)) = x : union xs (union ys zs)
union joinT3 (pairs t)
wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:
4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel

The compiler switch -fno-cse is used here to prevent space leak.

#### 3.10.1 Above Limit - Offset Sieve

Another task is to produce primes above a given value (i.e. not by their ordinal numbers):

{-# OPTIONS_GHC -O2 -fno-cse #-}
primesFromTMWE primes m = dropWhile (< m) [2,3,5,7,11]
++ gapsW a wh' (compositesFrom a)
where
(a,wh') = rollFrom (snapUp (max 3 m) 3 2)
(h,p':t) = span (< z) $drop 4 primes -- p < z => p*p<=a z = ceiling$ sqrt $fromIntegral a + 1 -- p'>=z => p'*p'>a compositesFrom a = joinT (joinST [multsOf p a | p <- h++[p']] : [multsOf p (p*p) | p <- t]) snapUp v o step = v + ((o-v) mod step) -- full steps from o multsOf p from = scanl (\c d->c+p*d) (p*x) wh -- map (p*)$
where                                             --   scanl (+) x wh
(x,wh) = rollFrom (snapUp from p (2*p) div p) --   , if p < from
wheelNums = scanl (+) 0 wheel
rollFrom n = go wheelNums wheel
where m = (n-11) mod 210
go (x:xs) ws@(w:ws') | x < m = go xs ws'
| True  = (n+x-m, ws)  -- (x >= m)

A certain preprocessing delay makes it worthwhile when producing more than just a few primes, otherwise it degenerates into simple trial division, which is then ought to be used directly:

primesFrom m = filter isPrime [m..]

### 3.11 Map-based

Runs ~1.7x slower than TME version, but with the same empirical time complexity, ~n1.2 (in n primes produced) and same very low (near constant) memory consumption:

import Data.List               -- based on http://stackoverflow.com/a/1140100
import qualified Data.Map as M

primesMPE :: [Integer]
primesMPE = 2:mkPrimes 3 M.empty prs 9   -- postponed addition of primes into map;
where                                  -- decoupled primes loop feed
prs = 3:mkPrimes 5 M.empty prs 9
mkPrimes n m ps@ ~(p:t) q = case (M.null m, M.findMin m) of
(False, (n', skips)) | n == n' ->
mkPrimes (n+2) (addSkips n (M.deleteMin m) skips) ps q
_ -> if n<q
then    n : mkPrimes (n+2)  m                  ps q

addSkip n m s = M.alter (Just . maybe [s] (s:)) (n+s) m
addSkips = foldl' . addSkip

## 4 Turner's sieve - Trial division

David Turner's original 1975 formulation (SASL Language Manual, 1975) replaces non-standard minus in the sieve of Eratosthenes by stock list comprehension with rem filtering, turning it into a kind of trial division algorithm:

-- unbounded sieve, premature filters
primesT = 2 : sieve [3,5..]  where
sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]
-- filter ((/=0).(remp)) xs

This creates an immense number of superfluous implicit filters in extremely premature fashion. To be admitted as prime, each number will be tested for divisibility here by all its preceding primes potentially, while just those not greater than its square root would suffice. To find e.g. the 1001st prime (7927), 1000 filters are used, when in fact just the first 24 are needed (up to 89's filter only). Operational overhead is enormous here.

### 4.1 Guarded Filters

But this really ought to be changed into bounded and guarded variant, again achieving the "miraculous" complexity improvement from above quadratic to about O(n1.45) empirically (in n primes produced):

primesToGT 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]

### 4.2 Postponed Filters

or as unbounded, postponed filters-creation variant:

primesPT = 2 : primes'
where
primes' = sieve [3,5..] 9 primes'
sieve (x:xs) q ps@ ~(p:t)
| x < q   = x : sieve xs q ps
| True    =     sieve [x | x <- xs, rem x p /= 0] (head t^2) t

creating here as well the linear nested structure at run-time, (...(([3,5..] >>= filterBy [3]) >>= filterBy [5])...), where filterBy ds n = [n | noDivs ds n] (see noDivs definition below)  –  but unlike the original code, each filter being created at its proper moment, not sooner than the prime's square is seen.

### 4.3 Optimal trial division

The above is equivalent to the traditional formulation of trial division,

noDivs factors n = foldr (\f r -> f*f > n || (rem n f /= 0 && r))
True factors
-- primes = filter (noDivs [2..]) [2..]
sieve x q ps k = let fs = take k $tail primes in filter ((all fs) . ((/=0).) . rem) [x,x+2..q-2] ++ sieve (q+2) (head ps^2) (tail ps) (k+1) This is usually faster than testing candidate numbers for divisibility one by one which has to re-fetch anew the needed prime factors to test by, for each candidate. Faster is the offset sieve of Eratosthenes on odds, and yet faster the above one, w/ wheel optimization. ### 4.5 Conclusions All these variants of course being variations of trial division – finding out primes by direct divisibility testing of every odd number by sequential primes below its square root (instead of just by its factors, which is what direct generation of multiples is doing, essentially) – are thus of principally worse complexities than that of Sieve of Eratosthenes. The prototype code is very inefficient, yet improving significantly with just a simple use of bounded, guarded formulation. So, there's no harm in applying simple improvements to a code instead of just labeling it "naive". BTW were divisibility testing somehow turned into an O(1) operation, e.g. by some kind of massive parallelization, the overall complexity of trial division sieve would drop to O(n). It's the sequentiality of testing that's the culprit. Did Eratosthenes himself achieve the optimal complexity? It rather seems doubtful, as he probably counted boxes in the table by 1 to go from one number to the next, as in 3,5,7,9,11,13,15, ... for he had no access even to Hindu numerals, using Greek alphabet for writing down numbers instead. Was he performing a genuine sieve of Eratosthenes then? Should faithfulness of an algorithm's implementation be judged by its performance? So the initial Turner code is just a one-liner that ought to have been regarded as executable specification in the first place. The reason it was taught that way is probably so that it could provoke discussion among students, at the very least discovering the optimization technique of the postponement of filter-creation. ## 5 Euler's Sieve ### 5.1 Unbounded Euler's sieve With each found prime Euler's sieve removes all its multiples in advance so that at each step the list to process is guaranteed to have no multiples of any of the preceding primes in it (consists only of numbers coprime with all the preceding primes) and thus starts with the next prime: primesEU = 2 : eulers [3,5..] where eulers (p:xs) = p : eulers (xs minus map (p*) (p:xs)) -- eratos (p:xs) = p : eratos (xs minus [p*p, p*p+2*p..]) This code is extremely inefficient, running above O(n2) empirical complexity (and worsening rapidly), and should be regarded a specification only. Its memory usage is very high, with empirical space complexity just below O(n2), in n primes produced. In the stream-based sieve of Eratosthenes we are able to skip along the input stream xs directly to the prime's square, consuming the whole prefix at once, thus achieving the results equivalent to the postponement technique, because the generation of the prime's multiples is independent of the rest of the stream. But here in the Euler's sieve it is dependent on all xs and we're unable in principle to skip along it to the prime's square - because all xs are needed for each prime's multiples generation. Thus efficient unbounded stream-based implementation seems to be impossible in principle, under the simple scheme of producing the multiples by multiplication. ### 5.2 Wheeled list representation The situation can be somewhat improved using a different list representation, for generating lists not from a last element and an increment, but rather a last span and an increment, which entails a set of helpful equivalences: {- fromElt (x,i) = x : fromElt (x + i,i) === iterate (+ i) x [n..] === fromElt (n,1) === fromSpan ([n],1) [n,n+2..] === fromElt (n,2) === fromSpan ([n,n+2],4) -} fromSpan (xs,i) = xs ++ fromSpan (map (+ i) xs,i) {- === concat$ iterate (map (+ i)) xs
fromSpan (p:xt,i) === p : fromSpan (xt ++ [p + i], i)
fromSpan (xs,i) minus fromSpan (ys,i)
=== fromSpan (xs minus ys, i)
map (p*) (fromSpan (xs,i))
=== fromSpan (map (p*) xs, p*i)
fromSpan (xs,i)   === forall (p > 0).
fromSpan (concat $take p$ iterate (map (+ i)) xs, p*i) -}

spanSpecs = iterate eulerStep ([2],1)
eulerStep (xs@(p:_), i) =
( (tail . concat . take p . iterate (map (+ i))) xs
minus map (p*) xs, p*i )

{- > mapM_ print $take 4 spanSpecs ([2],1) ([3],2) ([5,7],6) ([7,11,13,17,19,23,29,31],30) -} Generating a list from a span specification is like rolling a wheel as its pattern gets repeated over and over again. For each span specification w@((p:_),_) produced by eulerStep, the numbers in (fromSpan w) up to p2 are all primes too, so that eulerPrimesTo m = if m > 1 then go ([2],1) else [] where go w@((p:_), _) | m < p*p = takeWhile (<= m) (fromSpan w) | True = p : go (eulerStep w) This runs at about O(n1.5..1.8) complexity, for n primes produced, and also suffers from a severe space leak problem (IOW its memory usage is also very high). ## 6 Using Immutable Arrays ### 6.1 Generating Segments of Primes The sieve of Eratosthenes'es removal of multiples on each segment of odds can be done by actually marking them in an array instead of manipulating the ordered lists, and can be further sped up more than twice by working with odds only, represented as their offsets in segment arrays: import Data.Array -- import Data.Array.Unboxed primesSA = 2 : prs where prs = 3 : sieve prs 3 [] sieve (p:ps) x fs = [i*2 + x | (i,e) <- assocs a, e] ++ sieve ps (p*p) fs' where q = (p*p-x)div2 fs' = (p,0) : [(s, rem (y-q) s) | (s,y) <- fs] -- a :: UArray Int Bool a = accumArray (\ b c -> False) True (1,q-1) [(i,()) | (s,y) <- fs, i <- [y+s, y+s+s..q]] Run on Ideone.com it is somewhat faster than Tree Merging With Wheel in producing first million primes or two, but has worse time complexity and large memory footprint which quickly gets into hundreds of MBs. When the (commented out above) explicit type signature is added, making the same code work on unboxed arrays, the resulting GHC-compiled code runs more than twice faster and with better empirical complexity, of about O(n1.10..1.05) in producing first few millions of primes, with smaller though still growing memory footprint. Fixed sized segments are usually used in segmented sieves to limit the memory usage. ### 6.2 Calculating Primes Upto a Given Value Equivalent to Accumulating Array above, running somewhat faster (compiled by GHC with optimizations turned on): {-# OPTIONS_GHC -O2 #-} import Data.Array.Unboxed primesToNA n = 2: [i | i <- [3,5..n], ar ! i] where ar = f 5$ accumArray (\ a b -> False) True (3,n)
[(i,()) | i <- [9,15..n]]
f p a | q > n = a
| True  = if null x then a' else f (head x) a'
where q = p*p
a' :: UArray Int Bool
a'= a // [(i,False) | i <- [q, q+2*p..n]]
x = [i | i <- [p+2,p+4..n], a' ! i]

### 6.3 Calculating Primes in a Given Range

primesFromToA a b = (if a<3 then [2] else [])
++ [i | i <- [o,o+2..b], ar ! i]
where
o  = max (if even a then a+1 else a) 3
r  = floor . sqrt $fromIntegral b + 1 ar = accumArray (\a b-> False) True (o,b) [(i,()) | p <- [3,5..r] , let q = p*p s = 2*p (n,x) = quotRem (o - q) s q' = if o <= q then q else q + (n + signum x)*s , i <- [q',q'+s..b] ] Although using odds instead of primes, the array generation is so fast that it is very much feasible and even preferable for quick generation of some short spans of relatively big primes. ## 7 Using Mutable Arrays Using mutable arrays is the fastest but not the most memory efficient way to calculate prime numbers in Haskell. ### 7.1 Using ST Array This method implements the Sieve of Eratosthenes, similar to how you might do it in C, modified to work on odds only. It is fast, but about linear in memory consumption, allocating one (though apparently packed) sieve array for the whole sequence to process. import Control.Monad import Control.Monad.ST import Data.Array.ST import Data.Array.Unboxed sieveUA :: Int -> UArray Int Bool sieveUA top = runSTUArray$ do
let m = (top-1) div 2
r = floor . sqrt $fromIntegral top + 1 sieve <- newArray (1,m) True -- :: ST s (STUArray s Int Bool) forM_ [1..r div 2]$ \i -> do
when isPrime $do -- ((2*i+1)^2-1)div2 == 2*i*(i+1) forM_ [2*i*(i+1), 2*i*(i+2)+1..m]$ \j -> do
writeArray sieve j False
return sieve

primesToUA :: Int -> [Int]
primesToUA top = 2 : [i*2+1 | (i,True) <- assocs $sieveUA top] Its empirical time complexity is improving with n (number of primes produced) from above O(n1.20) towards O(n1.16). The reference C++ vector-based implementation exhibits this improvement in empirical time complexity too, from O(n1.5) gradually towards O(n1.12), where tested (which might be interpreted as evidence towards the expected quasilinearithmic O(nlog(n)log(logn)) time complexity). ### 7.2 Bitwise prime sieve with Template Haskell Count the number of prime below a given 'n'. Shows fast bitwise arrays, and an example of Template Haskell to defeat your enemies. {-# OPTIONS -O2 -optc-O -XBangPatterns #-} module Primes (nthPrime) where import Control.Monad.ST import Data.Array.ST import Data.Array.Base import System import Control.Monad import Data.Bits nthPrime :: Int -> Int nthPrime n = runST (sieve n) sieve n = do a <- newArray (3,n) True :: ST s (STUArray s Int Bool) let cutoff = truncate (sqrt$ fromIntegral n) + 1
go a n cutoff 3 1

go !a !m cutoff !n !c
| n >= m    = return c
| otherwise = do
if e then
if n < cutoff then
let loop !j
| j < m     = do
when x $unsafeWrite a j False loop (j+n) | otherwise = go a m cutoff (n+2) (c+1) in loop ( if n < 46340 then n * n else n shiftL 1) else go a m cutoff (n+2) (c+1) else go a m cutoff (n+2) c And place in a module: {-# OPTIONS -fth #-} import Primes main = print$( let x = nthPrime 10000000 in [| x |] )

Run as:

$ghc --make -o primes Main.hs$ time ./primes
664579
./primes  0.00s user 0.01s system 228% cpu 0.003 total

## 8 Implicit Heap

See Implicit Heap.

## 9 Prime Wheels

See Prime Wheels.