# Fastest prime generating algorithm

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

Is it faster than Sieve of Atkin?

-
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

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.

-
@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.

-
This is en.wikipedia.org/wiki/Wheel_factorization for n=2*3. – Iiridayn Nov 29 '14 at 19:12

The sieve of Eratosthenes is one of the most efficient ways to find all the prime number less than n.

Implemenation of Algorithm

-