<p>I want to find $n$ many different primes on RAM. I can find $O(\frac{n}{\log n})$ many primes in the interval $1$ to $n$ in $O(n)$ running time. A brute force way is to find $O(\frac{n}{\log n})$ many primes in the interval $1$ to $n$ and then next in $n+1$ to $2n$ and so on. If we find primes like in this way then overall running time will be $O(n \log n)$.</p>

<p><strong>Question :</strong> Is there any way to find $n$ many different primes in better than $O(n\log n)$ running time?</p>

CC BY-SA 4.0
2018-08-09T14:00:18.763Z
This is a great question!!  I asked a slightly related question a while back for finding relatively prime numbers: https://cstheory.stackexchange.com/questions/41005/how-hard-is-it-to-generate-a-set-of-relatively-prime-numbers-between-two-given-b
Michael Wehar
CC BY-SA 4.0
2018-08-09T14:16:24.373Z
You can save a $\log\log n$ factor by using the sieve of Atkin.
Emil Jeřábek
<ds.algorithms>
Finding $n$ many different primes efficiently
old
# Finding $n$ many different primes efficiently

(Asked by: username_0 on 2018-08-09)

I want to find $n$ many different primes on RAM. I can find $O(\frac{n}{\log n})$ many primes in the interval $1$ to $n$ in $O(n)$ running time. A brute force way is to find $O(\frac{n}{\log n})$ many primes in the interval $1$ to $n$ and then next in $n+1$ to $2n$ and so on. If we find primes like in this way then overall running time will be $O(n \log n)$.

**Question :** Is there any way to find $n$ many different primes in better than $O(n\log n)$ running time?

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: This is a great question!!  I asked a slightly related question a while back for finding relatively prime numbers: https://cstheory.stackexchange.com/questions/41005/how-hard-is-it-to-generate-a-set-of-relatively-prime-numbers-between-two-given-b  
> **username_2**: You can save a $\log\log n$ factor by using the sieve of Atkin.  

---

## 0 answers

