Is there any way or function to find out the number of primes numbers up to any number? (Say $10^7$ or $10^{30}$ or $200$ or $300$?)
$\endgroup$ 36 Answers
$\begingroup$$$\pi(n) \approx \frac{n}{\ln(n)}$$
where $\pi(n)$ is the number of primes less than $n$ and $\ln(n)$ is the natural logarithm of $n$. (Googling 'Prime Number Theorem' will tell you more! But this seems particularly nice for a one-page intro: )
$\endgroup$ 4 $\begingroup$One of the closest approximations to $\pi(x)$ is the log-integral, $\mathrm{Li}(x)$. The asymptotic expansion is easy to derive using integration by parts: $$ \begin{align} \mathrm{Li}(x) &=\int_2^n\frac{\mathrm{d}t}{\log(t)}\\ &=\frac{n}{\log(n)}+C_1+\int_2^n\frac{\mathrm{d}t}{\log(t)^2}\\ &=\frac{n}{\log(n)}+\frac{n}{\log(n)^2}+C_2+\int_2^n\frac{\mathrm{2\,d}t}{\log(t)^3}\\ &=\frac{n}{\log(n)}+\frac{n}{\log(n)^2}+\frac{2n}{\log(n)^3}+C_3+\int_2^n\frac{\mathrm{3!\,d}t}{\log(t)^4}\\ &=\frac{n}{\log(n)}\left(1+\frac1{\log(n)}+\frac2{\log(n)^2}+\dots+\frac{k!}{\log(n)^k}+O\left(\frac1{\log(n)^{k+1}}\right)\right) \end{align} $$ Thus, using the first two terms in the asymptotic series, $$ \begin{align} \frac{n}{\log(n)}\left(1+\frac1{\log(n)}+\dots\right) &=\frac{n}{\log(n)\left(1-\frac1{\log(n)}+\dots\right)}\\ &\approx\frac{n}{\log(n)-1} \end{align} $$ Therefore, $\dfrac{n}{\log(n)-1}$ is a better approximation than $\dfrac{n}{\log(n)}$ for large $n$.
$\endgroup$ 5 $\begingroup$The answers above are very correct and state the Prime Number Theorem. Note that below, $\pi(n)$ means the primes less than or equal to $n$. Pafnuty Chebyshev has shown that if $$\lim_{n \to \infty} {\pi(n) \over {n \over \ln(n)}}$$exists, it is $1$. There are a lot of values that are approximately equal to $\pi(n)$ actually, as shown in the table.
There is no known expicit formula for this, but we do know how this function behaves asymptotically, that is the famous prime-number theorem. It states that $$ \pi(n) \approx n/ln(n)$$
But there are certain algorithms for calculating this function. One such example is here Computing π(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method
$\endgroup$ 1 $\begingroup$There is an exact formula, but it requires an enormous amount of computer processing power for large values of $n$.
Starting from the prime indicator function (1 if $n$ is prime, 0 otherwise for integer $n$), which is given by the power series:
$$-8\sum _{h=1}^{\infty} n^{2h}\sum _{i=1}^h \log\zeta(2i)\sum _{v=i}^{h}\frac{(-1)^{h-v}(4\pi )^{2h-2v}}{\zeta(2v-2i)(2h+2-2v)!}$$
the prime counting function, $\pi(x)$, can then be easily derived by summing up the above function over $n$.
$$\pi(x)=-8\sum _{h=1}^{\infty} H_{-2h}(x)\sum _{i=1}^h \log\zeta(2i)\sum _{v=i}^{h}\frac{(-1)^{h-v}(4\pi )^{2h-2v}}{\zeta(2v-2i)(2h+2-2v)!}$$
where $H_{-2h}(x)$ is given by Faulhaber's formulas (not ugly at all, compared to other formulas out there.)
How do you prove the above prime indicator formula? That is the product of two functions, Moebius' $\mu(n)$ and an adjusted Von Mangoldt function, $\Lambda(n)/\log{n}$ (which yields 1/k at the prime powers, $p^k$, otherwise it yields 0, if $n$ is integer), which means $-\mu(n)\Lambda(n)/\log{n}$ is 1 at the primes and 0 otherwise.
Per a theorem known as The inversion formula for Dirichlet series, both these functions can be expressed as a function of the zeta function, and their product results in the function above.
But, there is a trade-off between exactness and computing easiness, the more you have of one the less you have of the other, hence the approximation formulas are more useful for large values.
ReferenceAn exact formula for the prime counting function
I've added a Mathematica formula for the prime indicator function, the reader can test it with values up to 6 ($n=1,...6$), if they have Mathematica. It will be 1 for integer $n$ prime, and 0 otherwise. (If you want to test higher values, T has to be increased.)
$MaxExtraPrecision = 200; T = 110; n = 6; N[-8*Sum[ n^(2*h)*Sum[ Log[Zeta[2*i]]* Sum[((-1)^(h - v)*(4*Pi)^(2*h - 2*v))/(Zeta[ 2*v - 2*i]*(2*h + 2 - 2*v)!), {v, i, h}], {i, 1, h}], {h, 1, T}], 5]let
$f(x)=\left\{2x+1: x\in \mathbb{N} \right\}$
$f(x)$ contains all positive odd numbers some of them are prime some are composite.
Now if $f(x)$ is composite as it is odd its factors must be odd means $f(x)=f(m)f(n)$ where $m,n\in \mathbb{N}.$
$\begin{align} 2x+1 &=(2m+1)(2n+1)\\ \implies 2x+1 &=4mn+2m+2n+1\\ \end{align}$
Means $x=2mn+m+n$
that means if $x$ is of form $2mn+m+n$ then $f(x)$ will give composite numbers otherwise prime no. so reduce the domain of $f(x)$ from $\mathbb{N}$ to $\mathbb{N}-A$ where $A$ is set of all numbers that can be represented as $2mn+m+n$, then we will get prime. Here $A$ can be calculated easily.
For example if $m=1, n=1$
Then $2mn+m+n$ that is $2(1)(1)+1+1=4$
So for $f(4)=9$ which is composite
But
\begin{align}
f(1) &=3\\
f(2)&=5\\
f(3)&=7\\
f(5)&=11\\
\end{align}
which are all primes
So for set $A$ given below function $f$ would take composite values and for set $\mathbb{N}-A$ which is set of natural numbers $-$ set $A$ function$f$ will give all prime values
$A\in\{4,7,10,12,13,16,17,19,22,24,25,27,28,31,32,34,37,38,40,42,43,45,46,47,49,52,55,57,58,59,60,61,62,64,66,67,70,\cdots \}$so to verify it\begin{align}
f(7) &=15\\
f(10) &=21\\
f(45) &=91\\
\end{align}so $\mathbb{N}-A\in \{1,2,3,5,6,8,9,11,14,15,18,20,21,23,26,29,33,35,36,39,41,44,48,50,51,53,54,56,63,65,68,69,\cdots\}$again to verify this\begin{align}
f(6) &=13\\
f(8) &=17\\
f(9) &=19\\
f(63) &=127\\
f(69) &=139\\
\end{align}which are all primes.
For $x\in \mathbb{N}-A$ range of $f(x)$ will be same as set of prime no.$f:\left(\mathbb{N}-A\right)→p$
$p\in \{3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,\cdots$
