prime_data/data/estimate/
nth_prime.rs

1use crate::data::utils::Logarithm;
2use std::ops::RangeInclusive;
3
4/// Approximates the "size" of the nth prime number.
5/// 
6/// I may or may not have
7/// [stolen this from Wikipedia](https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number)
8pub fn nth_prime_approximation(n: u64) -> u64 {
9
10    match n {
11        0 => panic!("Tried to get the zeroth prime!"),
12        1 => return 2,
13        2 => return 3,
14        3 => return 5,
15        _ => {}
16    };
17
18    let x = n as f64;
19    let logn = x.ln();
20    let loglogn = logn.ln();
21    let log2n = logn * logn;
22    let log2logn = loglogn * loglogn;
23
24    let term1 = (loglogn - 2.0) / logn;
25    let term2 = (log2logn - 6.0*loglogn + 11.0) / (2.0*log2n);
26
27    let approximation = x * (logn + loglogn - 1.0 + term1 - term2);
28
29    approximation as u64
30}
31
32/// Returns a range that contains the nth prime number
33/// 
34/// This is possible due to the fact that [`nth_prime_approximation`] converges to the actual nth prime as n grows
35/// over time, so we can ensure the error is at most some value epsilon.
36pub fn nth_prime_bounds(n: u64) -> RangeInclusive<u64> {
37
38    let log = Logarithm::log10(n);
39
40    if log < 4 {
41        0..=104723
42    } else {
43        let approximation = nth_prime_approximation(n);
44        let two: f64 = 2.0;
45        let relative_epsilon: f64 = match log {
46            4 => two.powi(-7),
47            5 => two.powi(-10),
48            6 => two.powi(-11),
49            7 => two.powi(-13),
50            _ => two.powi(-14),
51        };
52
53        let epsilon = (approximation as f64 * relative_epsilon) as u64;
54
55        (approximation - epsilon)..=(approximation + epsilon)
56    }
57}
prime_data/data/estimate/nth_prime.rs

prime_data/data/estimate/
nth_prime.rs
