16
$\begingroup$

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

Is it faster than Sieve of Atkin?

  • 1
    You can't generate all prime numbers nor an infinite subset of all prime numbers in finite time...2011-09-29
  • 4
    Ok, time to reopen2011-09-29
  • 0
    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.2012-11-16

4 Answers 4