## Fast method for computing the number of primes less than a given limit

HTML articles powered by AMS MathViewer

- by David C. Mapes PDF
- Math. Comp.
**17**(1963), 179-185 Request permission

## Abstract:

"Fast Method for Computing the Number of Primes Less Than a Given Limit” describes three processes used during the course of calculation. In the first part of the paper the author proves: \[ \phi (x,a) = \phi (x,1) - \phi ({\frac {x}{{{p_2}}},1}) - \phi ({\frac {x}{{{p_3}}},2}) - \ldots - \phi ({\frac {x}{{{p_a}}},a - 1})\] where $\phi (x,a)$ represents the number of numbers less than or equal to*x*and not divisible by the first “

*a*” primes. This identity is used to evaluate the formula $\pi (x) = \phi (x,a) + a - 1$, $a + 1 > \pi (\sqrt x )$ where resulting terms of the form $\phi (x’,a’)$ are broken down still further by the previously described method, or numerically evaluated using one or both of two other identities, the choice being dependent on $x’$ and $a’$. Following the paper is a table of calculations made using this process which gives the values of $\pi (x)$ for

*x*at intervals of 10 million up to 1000 million, along with the Riemann and the Chebyshev approximations for $\pi (x)$ and the amount they deviate from the true count.

## References

- D. H. Lehmer,
*On the exact number of primes less than a given limit*, Illinois J. Math.**3**(1959), 381–388. MR**106883**
D. N. Lehmer,

*List of Prime Numbers from 1 to 10,006,721*, New York, Hafner Pub. Co., 1956.

## Additional Information

- © Copyright 1963 American Mathematical Society
- Journal: Math. Comp.
**17**(1963), 179-185 - MSC: Primary 10.03; Secondary 10.42
- DOI: https://doi.org/10.1090/S0025-5718-1963-0158508-8
- MathSciNet review: 0158508