I'm not an advanced mathematician so I'm looking for some easy way . If there is no easy way . Then I'm doomed
4
-
$\begingroup$ Look up the prime counting function $\pi(x)$. $\endgroup$– J. M. ain't a mathematicianAug 28, 2017 at 5:05
-
1$\begingroup$ My students sometimes ask me for real-world applications of the math they study. I'd really like to know how failure to count the number of primes between two numbers leads to being "doomed". $\endgroup$– Eric TowersAug 28, 2017 at 5:17
-
1$\begingroup$ I was just kidding Eric Towers . I won't be doomed . I will be in this forum lurking around somewhere asking these kinds of questions. $\endgroup$– esquelAug 28, 2017 at 5:19
-
$\begingroup$ The "easy" way is to ask Wolfram Alpha. $\endgroup$– Robert IsraelAug 28, 2017 at 5:59
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
There is no "easy formula for it". There are easy approximations for large values one of them being $\pi(x) \approx x/ln(x)$ where $\pi(x)$ is the prime counting function.
Therefore between $a$ and $b$ there are approximately $\frac{b}{ln(b)} - \frac{a}{ln(a)}$ primes and this approximation gets better the large the values are.
For an exact answer, you could use the Miessnel-Lehmer algorithm but it is more complex.
See here for the Miessnel-Lehmer Algorithm:
https://en.wikipedia.org/wiki/Meissel%E2%80%93Lehmer_algorithm
$\begingroup$
$\endgroup$
1
Whether you are doomed or not depends on your definition of easy, and how approximate you can be. If there were a simple formula $p(x,y)$ for $x<y$ that gave you the number of primes between $x$ and $y$ integers, then by simply taking $\pi(y)=p(0,x)$ we would get a formula for computing precisely how many primes there are below a certain number. No such formula is know, thus there is no formula for the question you are asking. So, there is no easy way of precisely calculating the number of primes between to integers without testing the primality of every integer in between them. For small integers (say, below $1,000,000$), this is going to be "easy" for a not so powerful computer.
There are however approximations for the prime counting function given by $$\frac{x}{\ln{x}}<\pi(x)<\int_2^x\frac{1}{\ln(t)}dt$$ where both quantities converge to the exact value as $x$ becomes very large. Depending on how eactyou need to be, these approximations could be good enough (note that the integral converges much faster than the simple fraction, but depending on your tools available is not as easy to compute). To give an approximation for the number of primes between two integers ($x<y$) we would use the chosen approximatio for $\pi(x)$ and compute $\pi(y)-\pi(x)$.
For further information, see the wikipedia page on the prime counting function: https://en.wikipedia.org/wiki/Prime-counting_function
-
$\begingroup$ "For small integers (say, below 1.000,000)" . Yup those a small numbers . $\endgroup$– esquelAug 28, 2017 at 5:23