I am given two numbers $n,x$. I have to find the number of primes between them. Difference can be up to $10^6$; thus looping will take too much time. Is there any other way I can do it?

  • 1
    $\begingroup$ There are various approaches to prime counting, which is what your Question amounts to. $\endgroup$
    – hardmath
    Apr 11, 2017 at 15:54
  • $\begingroup$ @hardmath my math knowledge can't understand those arduous formulas,could you simplify them for me and future nincompoops? $\endgroup$
    – Murad
    Apr 11, 2017 at 16:03
  • $\begingroup$ There is a simple approximation (Prime Number Theorem), but an exact counting formula is necessarily more complicated. The famous Riemann hypothesis is connected with adjustments to the approximation that make it into an exact count. If you actually want to identify all the primes in a consecutive range, a segmented Sieve of Eratothenes or variant would be attractive. Which of these would you like to learn about? $\endgroup$
    – hardmath
    Apr 11, 2017 at 17:22
  • $\begingroup$ @Murad see here this answer to a similar question: math.stackexchange.com/a/777047/189215 $\endgroup$
    – iadvd
    Apr 12, 2017 at 0:27


You must log in to answer this question.

Browse other questions tagged .