アルゴリズムと数学 097

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bt

部分的にエラトステネスの篩を行うのはよくあることですが、1が入っていると処理が難しいので、Lが1なら2から始めることにしました。

// Primes in an Interval
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn make_prime_table(N: usize) -> Vec<usize> {
    let mut a: Vec<bool> = vec![true; N+1];
    for p in (2usize..).take_while(|&p| p*p <= N) {
        if !a[p] {
            continue
        }
        for m in (p*p..N+1).step_by(p) {
            a[m] = false
        }
    }
    (2..N+1).filter(|&n| a[n]).collect::<Vec<usize>>()
}

fn make_partial_prime_table(first: usize, last: usize) -> Vec<usize> {
    let primes = make_prime_table((last as f64).sqrt() as usize + 1);
    let mut a: Vec<bool> = vec![true; last-first];
    for p in primes.into_iter() {
        let m0 = (first + p - 1) / p * p;
        for m in (m0..last).step_by(p) {
            if m != p {
                a[m-first] = false
            }
        }
    }
    (first..last).filter(|&n| a[n-first]).collect::<Vec<usize>>()
}


//////////////////// process ////////////////////

fn read_input() -> (i64, i64) {
    let v: Vec<i64> = read_vec();
    let L = v[0];
    let R = v[1];
    (L, R)
}

fn f(L: i64, R: i64) -> usize {
    let first: usize = if L == 1 { 2 } else { L as usize };
    let last: usize = (R + 1) as usize;
    let partial_primes = make_partial_prime_table(first, last);
    partial_primes.len()
}

fn main() {
    let (L, R) = read_input();
    println!("{}", f(L, R))
}