prime_data/data/estimate/
upper_bound.rs

1use crate::data::utils::Logarithm;
2
3/// Estimates an upper bound for the amount of primes up to `bound`.
4/// 
5/// Sometimes, it's too costly to evaluate the amount of primes from 1 to N, especially in situations
6/// where a "good enough" estimate would suffice.
7/// 
8/// This function is guaranteed to give you a value greater or equal to the actual amount of prime numbers
9/// up to the given number. The relative error is also guaranteed to be `< 0.005`, but it gets better as
10/// the given number goes to infinity.
11pub fn upper_bound(bound: u64) -> u64 {
12    if bound <= 10_000 {
13        super::exact_count(bound)
14    } else {
15        match Logarithm::log10(bound) {
16            4 => offset_x_ln_x(bound, 1.109),
17            5 => offset_x_ln_x(bound, 1.100),
18            _ => pierre_dusart(bound, (1.00, 2.51)),
19        }
20    }
21}
22
23fn offset_x_ln_x(bound: u64, offset: f64) -> u64 {
24
25    let float = bound as f64;
26    let ln_x = float.ln();
27
28    (float / (ln_x - offset)) as u64
29}
30
31fn pierre_dusart(bound: u64, coef: (f64, f64)) -> u64 {
32
33    let float = bound as f64;
34    let ln_x = float.ln();
35    let x_ln_x = float / ln_x;
36    let inv_ln = ln_x.recip();
37    let inv_sq = inv_ln * inv_ln;
38
39    (x_ln_x * (1.0 + coef.0 * inv_ln + coef.1 * inv_sq)) as u64
40}
prime_data/data/estimate/upper_bound.rs

prime_data/data/estimate/
upper_bound.rs
