Prime Counting Function

Inputs

Upper limit

x

Any integer.

$\pi(x)=\#\{p\le x : p\text{ prime}\}$ , and $\pi(x)=0$ for $x<2$ . The count is exact: it is computed by Lehmer's method without listing the primes up to x. Computation runs locally in your browser.

Try

Result

—

π(x) = —

—

Prime number theorem comparison

Approximations, not exact values. The exact count is shown above; the two formulas below only estimate it. $\operatorname{Li}(x)=\int_2^x \frac{dt}{\ln t}$ (the offset logarithmic integral, starting at 2 — not the principal-value $\operatorname{li}(x)$ that starts at 0).

	Value	Error vs. $\pi(x)$	Relative error
Exact $\pi(x)$	—	—	—
$x/\ln x$ (approximation)	—	—	—
$\operatorname{Li}(x)$ (approximation)	—	—	—

To list the primes themselves rather than only count them, use Primes in a Range.

How it works

The prime-counting function $\pi(x)$ counts the primes $p\le x$ . For small $x$ the calculator builds a prime table up to $x$ and reads the answer off it. For larger $x$ it uses Lehmer's algorithm, which combines a partial sieve function $\varphi(x,a)$ with recursive prime counts, so $\pi(x)$ is obtained without generating every prime below $x$ . Only what the algorithm needs is generated: the primes up to $\sqrt{x}$ , and a bit-packed $\pi$ lookup table (up to about $x^{2/3}$ , at most $2\times10^{8}$ ) that answers small $\pi(y)$ instantly.

Write $p_1=2,\ p_2=3,\ \dots$ and let

\begin{aligned}&a=\pi\!\left(\lfloor x^{1/4}\rfloor\right),\qquad b=\pi\!\left(\lfloor\sqrt{x}\rfloor\right),\qquad c=\pi\!\left(\lfloor x^{1/3}\rfloor\right),\\&\varphi(x,a)=\#\{\,m\le x : \text{none of } p_1,\dots,p_a \text{ divides } m\,\}.\end{aligned}

Then Lehmer's formula is

\begin{aligned}\pi(x)&=\varphi(x,a)+\frac{(b+a-2)(b-a+1)}{2}-\sum_{i=a+1}^{b}\pi\!\left(\frac{x}{p_i}\right)\\&\quad-\sum_{i=a+1}^{c}\ \sum_{j=i}^{\pi\left(\sqrt{x/p_i}\right)}\left(\pi\!\left(\frac{x}{p_i p_j}\right)-(j-1)\right),\end{aligned}

with every quotient rounded down. $\varphi$ is evaluated with a lookup table for the first seven primes and the recurrence $\varphi(x,a)=\varphi(x,a-1)-\varphi\!\left(\lfloor x/p_a\rfloor,a-1\right)$ beyond that. Everything is exact integer arithmetic. The values $\pi(x/p_i)$ that fall above the lookup table are counted for $i>c$ in one pass of a segmented sieve up to about $x^{2/3}$ , and recursively by the same formula otherwise. Long computations are shared between several background workers, whose partial sums are added at the end. Requests whose predicted work or memory exceeds the calculator's browser limits (currently roughly $x\gtrsim 7\times10^{14}$ ) are refused rather than started.

Inputs

Result

Lehmer's ingredients for this x

How it works

Lehmer's ingredients for this $x$