Talk:Generation of primes

Proposed merger

Prime sieve is short and the content would fit well in the also short Generating primes. PrimeHunter 18:58, 5 December 2006 (UTC)[reply]

There were no comments after 6 weeks so I performed the merge today. PrimeHunter 17:28, 20 January 2007 (UTC)[reply]

Clarity

I am not sure of the proper verbage, but the article essentially is referring to generating consecutive primes, as opposing to generating a prime arbitrarily (just "some" prime), where the latter does not particularly lend itself to sieve techniques, or at the least there are many other techniques to generate an arbitrary prime more efficiently. I'm not xplaining well but the article would not apply to generation of such arbitrary primes. This might be worth clarifying.--Billymac00 (talk) 04:45, 14 January 2011 (UTC)[reply]

Complexity

Atkin and Bernstein 2004, p 1024, says "[the sieve of Eratosthenes] uses B bits of memory to compute the primes in an arithmetic progression of B numbers". That would make it O(N) space it seems, to compute primes from 2 to N. The article says O(N^1/2) space in the complexity section. This doesn't seem right. If it were to refer to the segmented sive, the storage for primes would become the main thing; it's $O(\pi ({\sqrt {N}}))=O(2{\sqrt {n}}/\log n)$ is it not? Anyone? WillNess (talk) 09:04, 20 July 2011 (UTC)[reply]

I find some of the wording of this section rather confusing... and it calls O(N log log N) sublinear so either the sublinear or the O(N log log N) is a mistake. Also maybe some of the material on the alternative sieves should be taken off the sieve of Eratosthenes page and put here then linked from there. (71.233.167.118 (talk) 02:45, 26 March 2016 (UTC))[reply]