Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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
MathSciNet review: 0158508
Full-text PDF

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:

$\displaystyle \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?)

  • [1] D. H. Lehmer, On the exact number of primes less than a given limit, Illinois J. Math. 3 (1959), 381–388. MR 0106883
  • [2] D. N. Lehmer, List of Prime Numbers from 1 to 10,006,721, New York, Hafner Pub. Co., 1956.

Similar Articles

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

American Mathematical Society