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

Author:
David C. Mapes

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

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

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

Retrieve articles in *Mathematics of Computation*
with MSC:
10.03,
10.42

Retrieve articles in all journals with MSC: 10.03, 10.42

Additional Information

Article copyright:
© Copyright 1963
American Mathematical Society