ISSN 1088-6842(online) ISSN 0025-5718(print)

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: "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 [Enhancements On Off] (What's this?)

• 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