[Math] Fastest prime generating algorithm

Question

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

Is it faster than Sieve of Atkin?

Answer 1

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.