What is the fastest known algorithm that generates all distinct prime numbers less than n?
Is it faster than Sieve of Atkin?
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.
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!
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.
|show 8 more comments|
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.