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$?)
How to find number of prime numbers up to to N?
-
2Ok, now I can understand the question. Dont shorten number with no. (especially not without the dot) ;) – 2012-12-24
6 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 )
-
0So let me get this straight: If I want to find the number or primes smaller than, say 10^100 - I'd have to first create a list of all primes smaller than 10^10, and then for every number (10^10,10^100) check them mod everything in said list (or against every member > sqrt(n) in that list)? – 2015-06-12
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
-
1There is a lot of variation in what counts as an "explicit formula"; a number of them can be seen at [wolfram alpha](http://www.wolframalpha.com/input/?i=primepi%28n%29). Of course, algorithms are usually much better than explicit formulas for actually calculating numerical values. – 2012-12-24
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$.
-
0@robjohn $\pi(x)$ is continuous also :p. – 2016-10-03
let
f(x)={ 2x+1 x∈ N }
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∈ N
2x+1=(2m+1)(2n+1)
2x+1=4mn+2m+2n+1
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 N to N-A where A is set of all no. 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 f(1)=3
f(2)=5
f(3)=7
f(5)=11 which are all primes
So for set A given below function f would take composite values and for set N-A which is set of natural no. - set A function f will give all prime values
A∈{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……………………..} so to verify it f(7)=15
f(10)=21
f(45)=91
so N-A∈ {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…………………………} again to verify this f(6)=13
f(8)=17
f(9)=19
f(63)=127
f(69)=139 which are all prime
for x∈ N-A range of f(x) will be same as set of prime no.f:(N-A)→p
p∈ {3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79………………
-
0Please see https://math.meta.stackexchange.com/questions/5020/ – 2018-10-12