17
$\begingroup$

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

Is it faster than Sieve of Atkin?

  • 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

12

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.

  • 3
    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...2012-11-16
1

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.

  • 0
    @sohaib, in essence it is enough to consider 2/6 = 1/3 of N to get all the primes below N (since we need to consider only the two progressions (6k+1) and (6k-1) and add 2 at the end to account for primes 2 and 3. One can even write pi(n)+c(n)=N/3. Here, c(n) is the number of composite within the two progressions. And there is an easy way to get those if you work with indices instead of numbers.2016-12-18
0

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

Implemenation of Algorithm

-1

Odd numbers can be wheeled in multiplications to output only odd composite numbers. Then the odd numbers that are not output are the prime numbers.

Now each inner loop can stop at a multiplication that reaches the value of an upper-bound and the outer loop can stop at the square root of the upper-bound.

Furthermore the loops from the number 11 can increment with 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10 ... as continuting and repeating. That's a big performance gain because multiples of 3, 5, and 7 are removed from the sequence of odd numbers.

A prime number application really works best when outputting prime numbers between an upper bound and the upper bound - n. Then the application appears to be just scrolling sections (or jumping to sections) of a list on each computation. And in this case the loop increments are really only needed on the outer loop because a single division operation jumps over unneeded sections of the inner loop. Of course, array subscript locations can work with translations such that the same array can handle any of the segmented computations and then not use very much memory.