8
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.