Formulas for prime counting between $n$ and $n^2$

85 Views Asked by At

Primes less than $n$ are known, are there some formulas counting primes between $n$ and $n^2$?

For sample formula, Primes less than $5$ is $2, 3$, number of primes between $5$ and $5^2$ is $5^2*(1-1/2)*(1-1/3)-1=7.333$, so there's approximate $7$ primes between $5$ and $5^2$.

1

There are 1 best solutions below

0
On

One notes, that you actually have to multiply by the distinct prime divisors of the difference to get an upper bound.

For example, in any set of 20 consecutive numbers you can only find at most: $$20\cdot(1-{1\over 2})\cdot(1-{1\over 5}) = 8$$ primes. This goes down, depending on where you start in the values, etc.

In $n^2-n$ you'll only have: $$\varphi(n-1)\cdot \varphi(n)$$ at the most (loose bounds). This gives the following bounds:

$$\begin{array}{c|c|c}n & n^2 & \varphi(n-1)\cdot\varphi(n)\\\hline 2 &4&1\\\hline 3&9&2\\\hline 4 &16&4\\\hline 5&25&8\\\hline 6&36&8\\\hline 7&49&12\\\hline 8 &64&24\\\hline 9&81&24\\\hline 10&100&24\\\hline 11&121&40\\\hline 12&144&40 \\\hline 13 &169&48\\\hline 14&196&72\end{array}$$

A more rigorous bound for some ( like the last few in the table), is using that there are only 8 in every 30, to conclude that there can't be more than 43 in 156, not 48. Likewise, there can't be more than more than 49 in 182, etc.

These are more bounds than an actual formula though. But, they are good enough in most cases I'd deal with. you might try to see what the prime number theorem says though.