48 lines
1.3 KiB
Text
48 lines
1.3 KiB
Text
// main.rs
|
|
mod bit_array;
|
|
mod prime_sieve;
|
|
|
|
use prime_sieve::PrimeSieve;
|
|
|
|
// See https://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number
|
|
fn upper_bound_for_nth_prime(n: usize) -> usize {
|
|
let x = n as f64;
|
|
(x * (x.ln() + x.ln().ln())) as usize
|
|
}
|
|
|
|
fn compute_transitions(limit: usize) {
|
|
use std::collections::BTreeMap;
|
|
let mut transitions = BTreeMap::new();
|
|
let mut prev = 2;
|
|
let mut count = 0;
|
|
let sieve = PrimeSieve::new(upper_bound_for_nth_prime(limit));
|
|
let mut n = 3;
|
|
while count < limit {
|
|
if sieve.is_prime(n) {
|
|
count += 1;
|
|
let digit = n % 10;
|
|
let key = (prev, digit);
|
|
if let Some(v) = transitions.get_mut(&key) {
|
|
*v += 1;
|
|
} else {
|
|
transitions.insert(key, 1);
|
|
}
|
|
prev = digit;
|
|
}
|
|
n += 2;
|
|
}
|
|
println!("First {} prime numbers:", limit);
|
|
for ((from, to), c) in &transitions {
|
|
let freq = 100.0 * (*c as f32) / (limit as f32);
|
|
println!(
|
|
"{} -> {}: count = {:7}, frequency = {:.2} %",
|
|
from, to, c, freq
|
|
);
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
compute_transitions(1000000);
|
|
println!();
|
|
compute_transitions(100000000);
|
|
}
|