AtCoder Beginner Contest 412 E

https://atcoder.jp/contests/abc412/tasks/abc412_e

素数か素数べきのときしかLCMは変わらないので、それをふるいで見つけます。

// LCM Sequence
#![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()
}


//////////////////// prime number ////////////////////

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>>()
}

// primeかprimeのpowerをVecにする
fn make_partial_pow_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 {
        let m0 = (first + p - 1) / p * p;
        for m1 in (m0..last).step_by(p) {
            let mut m = m1;
            if m == p {
                continue
            }
            while m > 1 {
                if m % p != 0 {
                    a[m1-first] = false;
                    break
                }
                m /= p
            }
        }
    }
    (first..last).filter(|&n| a[n-first]).collect::<Vec<usize>>()
}


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

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

fn F(L: usize, R: usize) -> usize {
    let prime_pow_table = make_partial_pow_prime_table(L+1, R+1);
    prime_pow_table.len() + 1
}

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