wiki-beurling-generalized-primes.rs

1use mrlycore::errors::Result;2use mrlyfig::{ink, plot, save, Board, Frame};3use mrlynum::classics::primes;4use mrlynum::formulas;56const TOP: usize = 100_000;7const SAMPLES: usize = 1000;89fn main() -> Result<()> {10    let mut board = Board::square();11    let frame = board.frame(0.08);12    let gap = frame.h * 0.08;13    let half = (frame.h - gap) / 2.0;14    let upper = Frame::new(frame.x, frame.y, frame.w, half);15    let lower = Frame::new(frame.x, frame.y + half + gap, frame.w, half);1617    let least = least_factor(TOP);18    let mut member = vec![false; TOP + 1];19    member[1] = true;20    for n in 2..=TOP {21        let p = least[n];22        member[n] = p % 4 == 1 && member[n / p];23    }24    let all_integers = counts(TOP, |_| true);25    let toy_integers = counts(TOP, |n| member[n]);26    let all_primes = counts(TOP, |n| n > 1 && least[n] == n);27    let toy_primes = counts(TOP, |n| n > 1 && least[n] == n && n % 4 == 1);2829    assert_eq!(all_integers[TOP], TOP);30    assert_eq!(toy_integers[TOP], 9623);31    assert_eq!(all_primes[TOP], formulas::prime_count(TOP));32    assert_eq!(all_primes[TOP], 9592);33    assert_eq!(toy_primes[TOP], 4783);34    assert_eq!(primes(TOP).len(), 9592);3536    trace(&mut board, upper, &all_integers, TOP as f64, ink::blue());37    trace(&mut board, upper, &toy_integers, TOP as f64, ink::yellow());38    let peak = all_primes[TOP] as f64;39    trace(&mut board, lower, &all_primes, peak, ink::blue());40    trace(&mut board, lower, &toy_primes, peak, ink::yellow());41    plot::axis(&mut board, upper, ink::line());42    plot::axis(&mut board, lower, ink::line());43    save("wiki-beurling-generalized-primes", &board)?;44    Ok(())45}4647fn least_factor(top: usize) -> Vec<usize> {48    let mut least: Vec<usize> = (0..=top).collect();49    let mut p = 2;50    while p * p <= top {51        if least[p] == p {52            for m in (p * p..=top).step_by(p) {53                if least[m] == m {54                    least[m] = p;55                }56            }57        }58        p += 1;59    }60    least61}6263fn counts(top: usize, keep: impl Fn(usize) -> bool) -> Vec<usize> {64    let mut out = vec![0; top + 1];65    for n in 1..=top {66        out[n] = out[n - 1] + keep(n) as usize;67    }68    out69}7071fn trace(board: &mut Board, frame: Frame, count: &[usize], peak: f64, color: mrlyfig::Color) {72    let top = count.len() - 1;73    let pts: Vec<(f64, f64)> = (0..=SAMPLES)74        .map(|k| {75            let x = top * k / SAMPLES;76            (77                frame.x + frame.w * x as f64 / top as f64,78                frame.y + frame.h * (1.0 - count[x] as f64 / peak),79            )80        })81        .collect();82    board.polyline(&pts, 3.4, color);83}