Misplaced Pages

Revision as of 23:41, 28 December 2004

In mathematics, a prime-counting function is any of many methods that count prime numbers.

Historically there are several such methods. Traditionally the prime counting function is given as ${\displaystyle \pi (x)}$, for instance, ${\displaystyle \pi (1000)=168}$ as there are 168 primes up to 1000.

Prime counting itself has been eclipsed by research on the Riemann Hypothesis formulated by Bernhard Riemann.

His work was a continuation of research relating prime numbers to continuous functions that included important figures like Carl Friedrich Gauss who along with others noticed that

${\displaystyle \pi (x)\approx {\frac {x}{\ln(x)}}}$

which lead to the relation known as the prime number theorem where an important figure in the history before Riemann is Pafnuty Chebyshev who used the Euler zeta function, which Riemann expanded into the complex plane by analytic continuation to get the Riemann zeta function.

One compact method for actually counting primes is the following recursive function:

With natural numbers x and y, if ${\displaystyle y\leq {\sqrt {x}}}$ then

${\displaystyle p(x,y)=\mathrm {floor} (x)-1-\sum _{k=2}^{y}{((p(x/k,k-1)-p(k-1,{\sqrt {k-1}}))(p(k,{\sqrt {k}})-p(k-1,{\sqrt {k-1}})))}}$

else ${\displaystyle p(x,y)=p(x,{\sqrt {x}})}$.

Here ${\displaystyle \pi (x)=p(x,{\sqrt {x}})}$ gives the count of prime numbers.

The method relies on the inclusion-exclusion principle as well as a few other ideas, and bears remarkable similarities to other less compactly represented prime counting functions, like Legendre's Formula discovered by the French mathematicians Adrien-Marie Legendre and Meissel's Formula discovered by the German mathematician Ernst Meissel.

The discrete summation is of a partial difference equation with the constraint that ${\displaystyle y\leq {\sqrt {x}}}$.

The method finds prime numbers as it recurses, and far faster algorithms can be developed from it by instead using a sieve like the Sieve of Eratosthenes to get the prime numbers up to ${\displaystyle {\sqrt {x}}}$ versus letting the formula find them.

Some values calculated for this article from one such algorithm:

${\displaystyle p(10,3)}$	4
${\displaystyle p(100,10)}$	25
${\displaystyle p(1000,31)}$	168
${\displaystyle p(10000,100)}$	1229
${\displaystyle p(10^{5},316)}$	9592
${\displaystyle p(10^{6},1000)}$	78498
${\displaystyle p(10^{7},3162)}$	664579
${\displaystyle p(10^{8},10^{4})}$	5761455
${\displaystyle p(10^{9},31622)}$	50847534
${\displaystyle p(10^{10},10^{5})}$	455052511
${\displaystyle p(10^{11},316227)}$	4118054813
${\displaystyle p(10^{12},10^{6})}$	37607912018

See also: floor function

• v
• t
• e