Function primal_estimate::prime_pi

pub fn prime_pi(n: u64) -> (u64, u64)

Returns estimated bounds for π(n), the number of primes less than or equal to n.

That is, if (a, b) = estimate_prime_pi(n), a ≤ π(n) ≤ b. The bounds used are proved in [1], [2, Théorème 1.10] (both summarised in [2, pp. 14–15]), and [3, Section 6.2].

[1]: Barkley Rosser. “Explicit Bounds for Some Functions of Prime Numbers”. American Journal of Mathematics 63 (1): 211–232. 1941. doi:10.2307/2371291.

[2]: Dusart, Pierre. “Autour de la fonction qui compte le nombre de nombres premiers.” PhD diss., Université de Limoges, 1998.

[3]: Dusart, Pierre. “Estimates of Some Functions Over Primes without R.H.” ArXiv:1002.0442. 2010.

Examples

// the number of primes below 1e9
let count_billion = 50_847_534;

let (low, high) = primal::estimate_prime_pi(1_000_000_000);
// check the bounds are satisfied
assert!(low <= count_billion && count_billion <= high);