Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Is it faster than Sieve of Atkin?

share|improve this question
    
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
3  
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

2 Answers 2

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.

share|improve this answer
    
Why "So no", I dont follow. –  grok_it Sep 29 '11 at 10:04
    
Because $n/\log \log n < n$. –  TonyK Sep 29 '11 at 10:20
    
less complexity only means that given a large enough n one algorithm will perform better than the other, but that do not mean that for a small n as 10^9 that will always be the case. –  Robert William Hanks Sep 29 '11 at 11:23
5  
@Robert: So? The question was about: asymptotic time complexity. The OP specifically used the notation O(n). –  TonyK Sep 29 '11 at 11:26
2  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.