# How to find number of prime numbers up to to N?

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$?)

-
I really do not understand your question. Please rephrase it and give an example of what you want? From what I understand, you are searching for a way to find a interval of N numbers out of which none is prime? – CBenni Dec 24 '12 at 11:52
I think you're looking for this en.wikipedia.org/wiki/Prime-counting_function. There is no known expicit formula for this, but we do how this function behaves asymptotically, that is the famous prime-number theorem en.wikipedia.org/wiki/Prime_number_theorem – Mohan Dec 24 '12 at 11:54
Ok, now I can understand the question. Dont shorten number with no. (especially not without the dot) ;) – CBenni Dec 24 '12 at 11:55

$$\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: http://primes.utm.edu/howmany.shtml#pnt )

-
 So no one till date found out the number of primes less than $n$ can be found out by using square root of $n$ too? and using some other numbers.. – Shan Dec 24 '12 at 12:32 @Shan Short answer: no! – Peter Smith Dec 24 '12 at 12:58

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

-
There is a lot of variation in what counts as an "explicit formula"; a number of them can be seen at wolfram alpha. Of course, algorithms are usually much better than explicit formulas for actually calculating numerical values. – Hurkyl Dec 24 '12 at 13:16

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.

-

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$.

-
 Why none of these give exact values for $π(x)$ ? – Shan Dec 26 '12 at 5:07 For one, $\pi(x)$ is a discrete function, taking only integer values, whereas $\mathrm{Li}(x)$ is continuous. Similarly, primes clump in certain places; however, $\frac{\mathrm{d}}{\mathrm{d}x}\mathrm{Li}(x)=\frac1{\log(x)}$ is monotonically decreasing. – robjohn♦ Dec 26 '12 at 13:30

I've discovered a marvelous algorithm for counting the primes up to N.

For each integer $n\leq N$, do the following:

1. Set $i=2$.
2. Reduce $n$ modulo $i$.
3. If you got zero in step 2, increase $n$ by 1 and go to step 1.
4. Increase $i$ by 1.
5. If $i\geq\sqrt{n}$, you've got a prime! Add 1 to your count, increase $n$ by 1. If $n\leq N$, kindly return to step 1.
-