# 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

1
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

1
Ok, now I can understand the question. Dont shorten number with no. (especially not without the dot) ;) – CBenni Dec 24 '12 at 11:55

## 5 Answers

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

-

1
– 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.
-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 32, "mathjax_display_tex": 5, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8864747881889343, "perplexity_flag": "middle"}