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?
