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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ This is a great question!! I asked a slightly related question a while back for finding relatively prime numbers: cstheory.stackexchange.com/questions/41005/… $\endgroup$
    – Michael Wehar
    Commented Aug 9, 2018 at 14:00
  • 3
    $\begingroup$ You can save a $\log\log n$ factor by using the sieve of Atkin. $\endgroup$
    – Emil Jeřábek
    Commented Aug 9, 2018 at 14:16

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.