Talk:Generating primes

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Priority
 Field:  Number theory

Proposed merger[edit]

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

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


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)


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 is it not? Anyone? WillNess (talk) 09:04, 20 July 2011 (UTC)

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. ( (talk) 02:45, 26 March 2016 (UTC))