Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the fastest known algorithm that generates all distinct prime numbers less than n?

Is it faster than Sieve of Atkin?

share|cite|improve this question
You can't generate all prime numbers nor an infinite subset of all prime numbers in finite time... – FUZxxl Sep 29 '11 at 9:02
Ok, time to reopen – grok_it Sep 29 '11 at 13:09
Sieve of Eratosthenes for reference takes O(n)+P(n)(n/k) time and P(n)log(n)+k space. Iteratively apply the sieve to the next k numbers; for each prime keep track of the smallest prime multiple you have seen. – Chad Brewbaker Nov 16 '12 at 16:27

2 Answers 2

What is the fastest known algorithm that generates all prime numbers?

I assume you mean: Given $n$, what is the fastest known algorithm that generates all prime numbers $p \le n$ ? Currently it is the Sieve of Atkin.

And what is the fastest known algorithm that generates any infinite subset of the prime numbers?

Again, I assume you mean: Given $n$, how fast can I generate $n$ distinct primes? There might be a faster method than the Sieve of Atkin, but I don't know of any. A good question!

And is there a theoretical lowest possible O(n) of such programs?

Is $n$ the number of primes you want to generate? Then it would take $O(n)$ operations just to store them in memory. So yes. But if you want to generate all primes $p \le n$ , the Sieve of Atkin has time complexity $O(n/\log \log n)$ . So no.

share|cite|improve this answer
@Robert: So? The question was about: asymptotic time complexity. The OP specifically used the notation O(n). – TonyK Sep 29 '11 at 11:26
In practice, the Atkin-Bernstein sieve isn't the fastest at any range. Sieve of Eratosthenes variants outperform it at all sizes. – Charles Sep 29 '11 at 13:19
@TonyK: I have only the highest respect for Dr. Bernstein--he does great theoretical work that is very practically accessible. But if you download yafu and primegen right now I think you'll see that yafu outperforms slightly for 32-bit limits and greatly outperforms above that point. – Charles Sep 29 '11 at 13:34
@TonyK: Yes, I realize that, that's what motivated me to test at those ranges. If you want a good comparison I suggest not only primegen, yafu, and whatever you write but also primesieve. – Charles Sep 29 '11 at 14:23
In base ten we know anything with more than one digit ending in 0,2,4,5,6,8 is nonprime. For tractable $n$ why not just use base 2*3*5*7*11*13*17*19...k? You can then make a suffix list of known nonprimes in the base up to k which you avoid, and from this you throw it against a sieve that includes everything you have found. Every so often you rebase. Ideally you want to use only P(n)*log(n) space. Atkin takes O(n) memory too... – Chad Brewbaker Nov 16 '12 at 16:03

I recently just chanced upon a particular logic. All prime numbers either fall in multiples of 6n+1 or 6n-1 except for 2 and 3.

Using this the search space could be considerably reduced for applying any sieve such as Atkins or Eratosthenes. Hence making it a slightly better form of finding primes.

share|cite|improve this answer
This is for n=2*3. – Iiridayn Nov 29 '14 at 19:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.