FLINT3.7.0-dev
/

n_prime_pi, n_prime_pi_bounds

Synopsis#include <flint/ulong_extras.h>
ulong n_prime_pi(ulong n)source
void n_prime_pi_bounds(ulong * lo, ulong * hi, ulong n)source

Return the number π(n)\pi(n) of primes p≤np \le n, or set lo≤π(n)≤hi\mathit{lo} \le \pi(n) \le \mathit{hi}.

n_prime_pi looks up small nn in a table; otherwise it extends the table of cached primes and performs a binary search.

n_prime_pi_bounds looks up small values in a table and otherwise uses the bounds n/ln⁡n<π(n)<1.25506 n/ln⁡nn / \ln n < \pi(n) < 1.25506\, n / \ln n of Rosser and Schoenfeld [RosSch1962], valid for n≥17n \ge 17. The bit length of nn is used to bound ln⁡n\ln n from the appropriate side. If lo and hi point to the same location, the upper bound is stored.

References#

  • [RosSch1962] Rosser, J. Barkley; Schoenfeld, Lowell: Approximate formulas for some functions of prime numbers. Illinois J. Math. 6 (1962), no. 1, 64–94.
Cite this page

The FLINT team, “n_prime_pi, n_prime_pi_bounds (ulong_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/ulong_extras/n_prime_pi.html (generated 2026-11-02).