20
$\begingroup$

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

  • 2
    Ok, now I can understand the question. Dont shorten number with no. (especially not without the dot) ;)2012-12-24

6 Answers 6

16

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

  • 0
    So 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
6

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.

enter image description here

5

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
    There 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
5

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
0

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………………

  • 0
    Please see https://math.meta.stackexchange.com/questions/5020/2018-10-12