Editing Sieve of Eratosthenes (section)

===Incremental sieve===
An incremental formulation of the sieve<ref name="ONeill">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}}, pp. 10, 11 (contains two incremental sieves in Haskell: a priority-queue–based one by O'Neill and a list–based, by Richard Bird).</ref> generates primes indefinitely (i.e., without an upper bound) by interleaving the generation of primes with the generation of their multiples (so that primes can be found in gaps between the multiples), where the multiples of each prime {{mvar|p}} are generated directly by counting up from the square of the prime in increments of {{mvar|p}} (or {{math|2''p''}} for odd primes). The generation must be initiated only when the prime's square is reached, to avoid adverse effects on efficiency. It can be expressed symbolically under the [[Dataflow programming|dataflow]] paradigm as

 ''primes'' = [''2'', ''3'', ...] \ [[''p''², ''p''²+''p'', ...] for ''p'' in ''primes''],

using [[list comprehension]] notation with <code>\</code> denoting [[Complement (set theory)#Relative complement|set subtraction]] of [[arithmetic progressions]] of numbers.

Primes can also be produced by iteratively sieving out the composites through [[Trial division|divisibility testing]] by sequential primes, one prime at a time. It is not the sieve of Eratosthenes but is often confused with it, even though the sieve of Eratosthenes directly generates the composites instead of testing for them. Trial division has worse theoretical [[Analysis of algorithms|complexity]] than that of the sieve of Eratosthenes in generating ranges of primes.<ref name="ONeill"/>

When testing each prime, the ''optimal'' trial division algorithm uses all prime numbers not exceeding its square root, whereas the sieve of Eratosthenes produces each composite from its prime factors only, and gets the primes "for free", between the composites. The widely known 1975 [[functional programming|functional]] sieve code by [[David Turner (computer scientist)|David Turner]]<ref>Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (<syntaxhighlight lang="haskell" inline>primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0</syntaxhighlight>). But see also [http://dl.acm.org/citation.cfm?id=811543&dl=ACM&coll=DL&CFID=663592028&CFTOKEN=36641676 Peter Henderson, Morris, James Jr., A Lazy Evaluator, 1976], where we [http://www.seas.gwu.edu/~rhyspj/cs3221/lab8/henderson.pdf find the following], attributed to P. Quarendon: <syntaxhighlight lang="python" inline>primeswrt[x;l] = if car[l] mod x=0 then primeswrt[x;cdr[l]] else cons[car[l];primeswrt[x;cdr[l]]] ; primes[l] = cons[car[l];primes[primeswrt[car[l];cdr[l]]]] ; primes[integers[2]]</syntaxhighlight>; the priority is unclear.</ref> is often presented as an example of the sieve of Eratosthenes<ref name="Runciman"/> but is actually a sub-optimal trial division sieve.<ref name="ONeill"/>