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 \pi(n) of primes p \le n, or set \mathit{lo} \le \pi(n) \le \mathit{hi}.

n_prime_pi looks up small n 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 < \pi(n) < 1.25506\, n / \ln n of Rosser and Schoenfeld [RosSch1962], valid for n \ge 17. The bit length of n is used to bound \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-10-20).