Sieve of Eratosthenes: Difference between revisions

The adding of each discovered prime's incremental step info to the mapping should be '''''postponed''''' until the prime's ''square'' is seen amongst the candidate numbers, as it is useless before that point. This drastically reduces the space complexity from <code>O(n)</code> to <code>O(sqrt(n/log(n)))</code>, in ''<code>n</code>'' primes produced, and also lowers the run time complexity quite low ([http://ideone.com/t0vVqVXep9F this test entry] shows about <code>O(n^1.08)</code> [http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth empirical order of growth] which is very close to the theoretical value of <code>O(n log(n) log(log(n)))</code>, in ''<code>n</code>'' primes produced):

yield 2 ; yield 3 ; yield 5 ; yield 7 ;

psbps = (p for p in primes()) # additional primes supply

p = ps.next(bps) and ps.next(bps) # discard 2, then get 3

q = p *p p # 9 - square of next prime to be put

n = 9 # the initial candidate number

if n < q: # n is prime

yield n # n is prime

add(sieve,p2 q= p + 2*p, 2*p) # n == p * p: for prime p, underadd p * p + 2 * p,

psieve[q + p2] = ps.next()p2 # # add with 2 * p as incremental step

p = next(bps); q = p * p # advance base prime and next prime to be put

s = sieve.pop(n); nxt = n + s # n is composite, advance

add(while nxt in sieve,: nnxt += s, s) # ensure each entry is unique