<p>Given $n$, let $M = 2n\log n$ (here $2$ is any constant larger than $1$). Put all numbers from $2$ to $M$ in a linked list. Now implement Eratosthenes sieve, by repeatedly running the following algorithm, until you get $n$ primes. Look for the first unmarked number $p$ (they all start unmarked; start looking at the previous prime), take it as a prime, and mark every integer in hops of length $p$. The running time is roughly $M + \sum_p M/p = \Theta(M\log\log M) = \Theta(n \log n \log\log n)$, where $p$ goes over the first $n$ primes. Since the $k$th prime $p_k$ is about $k\log k$, heuristically indeed
$$ \sum_{k=1}^n \frac{1}{p_k} \approx \sum_{k=2}^n \frac{1}{k\log k} \approx \int_2^n \frac{dk}{k\log k} \approx \log\log n.$$
This approximation can be proved rigorously, this is one of the results known as Mertens' theorem.</p>

<p>See Emil's comment below or the Wikipedia article for improvements on this algorithm.</p>

<p>Edit: Before Emil's comment, I suggested implementing the algorithm using a linked list, but that's a bad suggestion since you can't "hop" in a linked list, causing the runtime to be $\Omega(n^2)$.</p>

CC BY-SA 3.0
2012-11-01T08:02:55.960Z
Question: So if the number of primes we want to find from 1 is $n$, we must be able to find all of them in the range of $2n \log n$?
Dotto
CC BY-SA 3.0
2012-11-01T08:52:22.253Z
@Dotto: see https://en.wikipedia.org/wiki/Prime_number_theorem#Bounds_on_the_prime-counting_function
András Salamon
CC BY-SA 3.0
2012-11-01T17:53:53.273Z
A straightforward implementation of the usual Eratosthenes sieve algorithm runs in time $O(M\log\log M)=O(n\log n\log\log n)$. One can remove the factor of $\log\log n$ by using wheel factorization. Moreover, one can reduce the space complexity of the algorithm to something like $O(\sqrt M)$ by consecutively sieving intervals of about such length. So, the implementation with linked lists is horribly inefficient in comparison.
Emil Jeřábek
CC BY-SA 3.0
2012-11-02T03:06:41.450Z
Emil's right, I was imagining a sequential implementation, which is quite a dumb idea...
Yuval Filmus
CC BY-SA 3.0
2012-11-01T05:05:57.637Z
2012-11-02T03:14:43.707Z
2012-11-02T03:14:43.707Z
Yuval Filmus
<p>There is an algorithm due to Atkin and Bernstein. It computes prime numbers up to $N$ using $O(\dfrac{N}{\log \log N})$ additions and $N^{1/2+o(1)}$ bits of memory. </p>

<p>The Wikipedia article on <a href="http://en.wikipedia.org/wiki/Sieve_of_Atkin" rel="nofollow">Sieve of Atkin</a> gives pseudocode (caveat: see the comments). For more, see their paper <a href="http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf" rel="nofollow">A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030</a>.</p>

CC BY-SA 3.0
2012-11-01T18:00:21.663Z
The pseudocode on Wikipedia is totally unsuitable for a real implementation (as is actually mentioned there). The $\log\log N$ saving the algorithm has over the sieve of Eratosthenes crucially relies on the fact that one does *not* have to go through all pairs $(x,y)$ to select those that lie on the three quadratics as is done in the pseudocode, but one can actually trace the quadratics directly using an algorithm similar to the one used e.g. to pixelize circles. This is explained in the Atkin & Bernstein paper. If you ignore this, then the algorithm will have the same asymptotic complexity...
Emil Jeřábek
CC BY-SA 3.0
2012-11-01T18:05:32.270Z
...as the (much simpler) sieve of Eratosthenes, and the implied constants will be significantly worse. It is in fact quite nontrivial to implement the sieve of Atkin properly so that it is actually faster than Eratosthenes, and it requires understanding of what is going on. A very fast optimized implementation due to D.J.Bernstein (who is a coauthor of the paper and known as a skilled programmer) is available at http://cr.yp.to/primegen.html .
Emil Jeřábek
CC BY-SA 3.0
2012-11-01T18:41:39.523Z
Oh, and of course, as in the case of Eratosthenes sieve, the asymptotic bounds you (or rather Atkin and Bernstein) give depend on wheel factorization (amounting to a $\log\log N$ factor in running time) and sieving in smaller chunks (otherwise the space complexity is $O(N)$). Neither of these is implemented in the pseudocode.
Emil Jeřábek
CC BY-SA 3.0
2012-11-01T20:16:56.510Z
@EmilJeřábek Wait, *for a real implementation*? A real implementation doesn't mean it has a high-performance requirements. For some purposes, an algorithm that works fairly fast is perfectly fine. The question did not specify exact requirements. You are of course right that it always makes sense to use implementations that are proven to be fast and many people use them.
Juho
CC BY-SA 3.0
2012-11-01T20:26:40.407Z
It is quite pointless to make a slow implementation of the sieve of Atkin when you can make a faster implementation of the sieve of Eratosthenes with much less effort.
Emil Jeřábek
CC BY-SA 3.0
2012-11-01T14:21:24.900Z
2015-08-16T10:28:07.490Z
2015-08-16T10:28:07.490Z
Juho
<p>Is there any way to get $n$ primes efficiently? That is, is there any polynomial algorithm for doing this? ($n$ is the cardinality.)</p>

<p>Re-phrasing the question:</p>

<p>1) Suppose that at the input level, we insert $n$. This is the number of primes we want to obtain. (any set) (So, for example, getting five number of prime. The example output would be 2,3,5,7,11)</p>

<p>2) Is there any algorithm that does this efficiently? What would be its complexity (based on $n$)?</p>

CC BY-SA 3.0
2012-11-01T04:01:52.210Z
If the input is n in binary, then the output is exponentially long. If the input is n in unary, the just run the algorithm to get one prime repeatedly.
Tyson Williams
CC BY-SA 3.0
2012-11-01T04:19:11.313Z
What I was asking is whether there are some efficient ways to get, for example, 19 primes. Or 20 primes or so. I am not getting how $n$ being unary or binary matters....
Dotto
CC BY-SA 3.0
2012-11-01T04:58:45.410Z
Use the Eratosthenes sieve.
Yuval Filmus
CC BY-SA 3.0
2012-11-01T10:00:17.090Z
@Dotto : If the input number is given in binary, then the length of the input is log n, hence any algorithm running in polynomial of n, would become exponential in the input length as 2^{log n} = n. Hence the running time depends on the representation of the input.
Sajin Koroth
CC BY-SA 3.0
2015-08-16T12:07:31.490Z
Assume $n$ is parameter here. If you can effectivize Green-Tao theorem, you can get $n$-primes in linear time.
Turbo
<cc.complexity-theory>
An algorithm for getting $n$ primes
Dotto
# An algorithm for getting $n$ primes

(Asked by: username_0 on 2012-11-01)

Is there any way to get $n$ primes efficiently? That is, is there any polynomial algorithm for doing this? ($n$ is the cardinality.)

Re-phrasing the question:

1) Suppose that at the input level, we insert $n$. This is the number of primes we want to obtain. (any set) (So, for example, getting five number of prime. The example output would be 2,3,5,7,11)

2) Is there any algorithm that does this efficiently? What would be its complexity (based on $n$)?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: If the input is n in binary, then the output is exponentially long. If the input is n in unary, the just run the algorithm to get one prime repeatedly.  
> **username_0**: What I was asking is whether there are some efficient ways to get, for example, 19 primes. Or 20 primes or so. I am not getting how $n$ being unary or binary matters....  
> **username_2**: Use the Eratosthenes sieve.  
> **username_3**: @username_0 : If the input number is given in binary, then the length of the input is log n, hence any algorithm running in polynomial of n, would become exponential in the input length as 2^{log n} = n. Hence the running time depends on the representation of the input.  
> **username_4**: Assume $n$ is parameter here. If you can effectivize Green-Tao theorem, you can get $n$-primes in linear time.  

---

## 2 answers

### Answer by username_2 on 2012-11-01. Score: 10

Given $n$, let $M = 2n\log n$ (here $2$ is any constant larger than $1$). Put all numbers from $2$ to $M$ in a linked list. Now implement Eratosthenes sieve, by repeatedly running the following algorithm, until you get $n$ primes. Look for the first unmarked number $p$ (they all start unmarked; start looking at the previous prime), take it as a prime, and mark every integer in hops of length $p$. The running time is roughly $M + \sum\_p M/p = \Theta(M\log\log M) = \Theta(n \log n \log\log n)$, where $p$ goes over the first $n$ primes. Since the $k$th prime $p\_k$ is about $k\log k$, heuristically indeed
$$ \sum\_{k=1}^n \frac{1}{p\_k} \approx \sum\_{k=2}^n \frac{1}{k\log k} \approx \int\_2^n \frac{dk}{k\log k} \approx \log\log n.$$
This approximation can be proved rigorously, this is one of the results known as Mertens' theorem.

See Emil's comment below or the Wikipedia article for improvements on this algorithm.

Edit: Before Emil's comment, I suggested implementing the algorithm using a linked list, but that's a bad suggestion since you can't "hop" in a linked list, causing the runtime to be $\Omega(n^2)$.

> **Comments:**
> **username_0**: Question: So if the number of primes we want to find from 1 is $n$, we must be able to find all of them in the range of $2n \log n$?  
> **username_5**: @username_0: see https://en.wikipedia.org/wiki/Prime_number_theorem#Bounds_on_the_prime-counting_function  
> **username_6**: A straightforward implementation of the usual Eratosthenes sieve algorithm runs in time $O(M\log\log M)=O(n\log n\log\log n)$. One can remove the factor of $\log\log n$ by using wheel factorization. Moreover, one can reduce the space complexity of the algorithm to something like $O(\sqrt M)$ by consecutively sieving intervals of about such length. So, the implementation with linked lists is horribly inefficient in comparison.  
> **username_2**: Emil's right, I was imagining a sequential implementation, which is quite a dumb idea...  

---

### Answer by username_7 on 2012-11-01. Score: 5

There is an algorithm due to Atkin and Bernstein. It computes prime numbers up to $N$ using $O(\dfrac{N}{\log \log N})$ additions and $N^{1/2+o(1)}$ bits of memory.

The Wikipedia article on [Sieve of Atkin](http://en.wikipedia.org/wiki/Sieve_of_Atkin) gives pseudocode (caveat: see the comments). For more, see their paper [A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030](http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf).

> **Comments:**
> **username_6**: The pseudocode on Wikipedia is totally unsuitable for a real implementation (as is actually mentioned there). The $\log\log N$ saving the algorithm has over the sieve of Eratosthenes crucially relies on the fact that one does *not* have to go through all pairs $(x,y)$ to select those that lie on the three quadratics as is done in the pseudocode, but one can actually trace the quadratics directly using an algorithm similar to the one used e.g. to pixelize circles. This is explained in the Atkin & Bernstein paper. If you ignore this, then the algorithm will have the same asymptotic complexity...  
> **username_6**: ...as the (much simpler) sieve of Eratosthenes, and the implied constants will be significantly worse. It is in fact quite nontrivial to implement the sieve of Atkin properly so that it is actually faster than Eratosthenes, and it requires understanding of what is going on. A very fast optimized implementation due to D.J.Bernstein (who is a coauthor of the paper and known as a skilled programmer) is available at http://cr.yp.to/primegen.html .  
> **username_6**: Oh, and of course, as in the case of Eratosthenes sieve, the asymptotic bounds you (or rather Atkin and Bernstein) give depend on wheel factorization (amounting to a $\log\log N$ factor in running time) and sieving in smaller chunks (otherwise the space complexity is $O(N)$). Neither of these is implemented in the pseudocode.  
> **username_7**: @EmilJeřábek Wait, *for a real implementation*? A real implementation doesn't mean it has a high-performance requirements. For some purposes, an algorithm that works fairly fast is perfectly fine. The question did not specify exact requirements. You are of course right that it always makes sense to use implementations that are proven to be fast and many people use them.  
> **username_6**: It is quite pointless to make a slow implementation of the sieve of Atkin when you can make a faster implementation of the sieve of Eratosthenes with much less effort.  

---

