Talk:Generation of primes

How can Mathematica calculate the n’th prime fairly quickly. It can calculate the 10^14 prime in less than 3 seconds on a low end i7 computer made around 2015-2020.

Obviously, Mathematica doesn't use even the fastest implementation of a sieve such as the Sieve of Eratosthenes, of which the fastest (such as Kim Walich's primesieve) would take hours, or at least not only a sieve. What is almost certainly done by the Mathematica algorithm is to do a close estimate of a prime just under the desired one (there are many formulas for this of increasing complexity with increasing accuracy) which will take a fraction of a second to get this estimate. Then, a prime count algorithm is used to get the exact number of primes up to that estimate, such as Kim Walich's primecount in about a second. Then one can use a sieve such as primesieve to sieve a narrow interval above the estimate sufficient to include the desired prime, which only requires knowing the base prime up to the square root or 10 ^ 7, and is very fast, taking only a fraction of a second. Kim Walich's primecount has an option to bundle all of this to produce large nth primes very quickly by this method. GordonBGood 05-12-2024 — Preceding unsigned comment added by GordonBGood (talk • contribs) 15:08, 5 December 2024 (UTC)[reply]

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]