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

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – CBenni
    Commented Dec 24, 2012 at 11:52
  • 2
    $\begingroup$ 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 $\endgroup$
    – Mohan
    Commented Dec 24, 2012 at 11:54
  • 2
    $\begingroup$ Ok, now I can understand the question. Dont shorten number with no. (especially not without the dot) ;) $\endgroup$
    – CBenni
    Commented Dec 24, 2012 at 11:55

7 Answers 7

25
$\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: https://primes.utm.edu/howmany.html )

$\endgroup$
3
  • $\begingroup$ 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.. $\endgroup$
    – Shan
    Commented Dec 24, 2012 at 12:32
  • $\begingroup$ @Shan Short answer: no! $\endgroup$ Commented Dec 24, 2012 at 12:58
  • $\begingroup$ 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)? $\endgroup$ Commented Jun 12, 2015 at 11:09
11
$\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$ Why none of these give exact values for $π(x)$ ? $\endgroup$
    – Shan
    Commented Dec 26, 2012 at 5:07
  • $\begingroup$ 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. $\endgroup$
    – robjohn
    Commented Dec 26, 2012 at 13:30
  • $\begingroup$ @robjohn $\pi(x)$ is continuous also :p. $\endgroup$ Commented Oct 3, 2016 at 2:25
  • $\begingroup$ @YoTengoUnLCD Sorry, I'm confused. How can π(x) be continuous? $\endgroup$ Commented Feb 26, 2021 at 22:40
  • $\begingroup$ Any function on a discrete set is vacuously continuous. $\endgroup$
    – robjohn
    Commented Feb 26, 2021 at 23:26
10
$\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.

enter image description here

$\endgroup$
5
$\begingroup$

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
  • 1
    $\begingroup$ 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. $\endgroup$
    – user14972
    Commented Dec 24, 2012 at 13:16
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.

Reference An 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]
$\endgroup$
3
  • 1
    $\begingroup$ Hi, as it is your paper doesn't fit the standards, I opened a discussion to show why and give you the opportunity to simplify your formula (and its derivation) $\endgroup$
    – reuns
    Commented Jan 1, 2020 at 4:12
  • 1
    $\begingroup$ I gave a two line proof of your formula... The problem is that you don't have the experience about proofs and proof writing (I do because I am on math forums since more than 3 years) math.stackexchange.com/users/276986/reuns?tab=answers $\endgroup$
    – reuns
    Commented Jan 1, 2020 at 5:22
  • $\begingroup$ the link is dead $\endgroup$ Commented Oct 21, 2022 at 10:56
0
$\begingroup$

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$

$\endgroup$
1
0
$\begingroup$

One simple way is to use the Sieve of Eratosthenes in $O(n \log \log n)$ time or linear sieve in $O(n)$ time and count the number of primes found.

The prime-counting function $\pi(n)$ can be computed exactly in sub-linear time, allowing computation of $\pi(10^8), \pi(10^9), \dots$ using the Meissel-Lehmer algorithm.

The starting point is the observation by Legendre via inclusion-exclusion that the number of integers $\le x$ divisible by no prime $p_i \le \sqrt x$ is

$$ \left(\lfloor x \rfloor - \sum_i \left\lfloor \frac{x}{p_i} \right\rfloor + \sum_{i<j} \left\lfloor \frac{x}{p_i p_j} \right\rfloor - \cdots \right) - 1 = \pi(x) - \pi(\sqrt x) $$

The $-1$ adjusting for the fact the LHS counts $1$ among the "primes".

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .