<p>If by efficient you mean more practical space-wise for large bounds, check the <a href="http://digitalcommons.butler.edu/cgi/viewcontent.cgi?article=1095&amp;context=facsch_papers" rel="nofollow">Pseudosquares Prime Sieve</a>.</p>

<p>This (given enough time) allows searching for much larger prime numbers.</p>

CC BY-SA 3.0
2014-01-10T23:51:42.333Z
2014-01-10T23:51:42.333Z
R B
<p>I know about algorithms like <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow">Sieve of Eratosthenes</a> and <a href="http://en.wikipedia.org/wiki/Sieve_of_Atkin" rel="nofollow">Sieve of Atkin</a> for <a href="http://en.wikipedia.org/wiki/Generating_primes" rel="nofollow">generating prime numbers</a>.</p>

<p>I would like to know what is the most efficient known algorithm to generate the sequence of $k$ distinct prime numbers all of which are larger than a given number $n$?</p>

CC BY-SA 3.0
2014-01-10T18:22:46.747Z
Do you want to find a prime number or check if a given number is prime ?
Suresh Venkat
CC BY-SA 3.0
2014-01-10T19:50:13.257Z
Hi, I want to find a prime number
user17629
CC BY-SA 3.0
2014-01-10T23:36:50.810Z
Please check these links, and see if they suite your needs: [Generating primes](http://en.wikipedia.org/wiki/Generating_primes), [Efficient Prime Number Generating Algorithms](http://en.wikibooks.org/wiki/Efficient_Prime_Number_Generating_Algorithms), and [How can I generate large prime numbers for RSA](http://crypto.stackexchange.com/questions/71/how-can-i-generate-large-prime-numbers-for-rsa).
Sadeq Dousti
CC BY-SA 3.0
2014-01-12T02:29:28.163Z
int main() { return 17; }
Jeffε
CC BY-SA 3.0
2014-01-12T23:59:30.707Z
@RickyDemer Sure, but OP clarified: "_I want to find a prime number_"
Jeffε
CC BY-SA 3.0
2014-01-19T19:34:19.477Z
The most recent edit still leaves the question unclear.  Do you want the sequence of all prime numbers, an infinite sequence of distinct prime numbers, a sequence containing a certain number of prime numbers, or something else entirely?  The trivial algorithm "Return the empty sequence" solves the problem as written.
Jeffε
<ds.algorithms><cr.crypto-security><nt.number-theory>
What is the most efficient algorithm to generate a sequence of prime numbers?
user17629
# What is the most efficient algorithm to generate a sequence of prime numbers?

(Asked by: username_0 on 2014-01-10)

I know about algorithms like [Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) and [Sieve of Atkin](http://en.wikipedia.org/wiki/Sieve_of_Atkin) for [generating prime numbers](http://en.wikipedia.org/wiki/Generating_primes).

I would like to know what is the most efficient known algorithm to generate the sequence of $k$ distinct prime numbers all of which are larger than a given number $n$?

**Tags:** ds.algorithms, cr.crypto-security, nt.number-theory

> **Comments:**
> **username_1**: Do you want to find a prime number or check if a given number is prime ?  
> **username_0**: Hi, I want to find a prime number  
> **username_2**: Please check these links, and see if they suite your needs: [Generating primes](http://en.wikipedia.org/wiki/Generating_primes), [Efficient Prime Number Generating Algorithms](http://en.wikibooks.org/wiki/Efficient_Prime_Number_Generating_Algorithms), and [How can I generate large prime numbers for RSA](http://crypto.stackexchange.com/questions/71/how-can-i-generate-large-prime-numbers-for-rsa).  
> **username_3**: int main() { return 17; }  
> **username_3**: @RickyDemer Sure, but OP clarified: "_I want to find a prime number_"  
> **username_3**: The most recent edit still leaves the question unclear.  Do you want the sequence of all prime numbers, an infinite sequence of distinct prime numbers, a sequence containing a certain number of prime numbers, or something else entirely?  The trivial algorithm "Return the empty sequence" solves the problem as written.  

---

## 1 answers

### Answer by username_4 on 2014-01-10. Score: 3

If by efficient you mean more practical space-wise for large bounds, check the [Pseudosquares Prime Sieve](http://digitalcommons.butler.edu/cgi/viewcontent.cgi?article=1095&context=facsch_papers).

This (given enough time) allows searching for much larger prime numbers.


---

