AtCoder Beginner Contest 383 D

https://atcoder.jp/contests/abc383/tasks/abc383_d

次のように素因数分解すると、

約数の個数は、

となります。なので、との形しかありえません。。

// 9 Divisors
#![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 int_sqrt(n: usize) -> usize {
    let mut x = (n + 1) / 2;
    loop {
        let x1 = (x + n / x) / 2;
        if x1 >= x {
            return x
        }
        x = x1
    }
}


//////////////////// prime ////////////////////

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

fn count_primes(primes: &Vec<usize>, N: usize) -> Vec<usize> {
    let mut pi: Vec<usize> = vec![0; N+1];
    let mut prev: usize = 0;
    for &p in primes.iter() {
        for n in prev+1..p {
            pi[n] = pi[n-1]
        }
        pi[p] = pi[p-1] + 1;
        prev = p
    }
    for n in prev+1..N+1 {
        pi[n] = pi[n-1]
    }
    pi
}


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

fn F(N: usize) -> usize {
    let M = int_sqrt(N) / 2;
    let primes = make_prime_table(M);
    let pi = count_primes(&primes, M);
    
    let mut counter: usize = 0;
    // p^8
    for &p in primes.iter() {
        if p.pow(8) > N {
            break
        }
        counter += 1
    }
    
    // p^2q^2
    for i in 0..primes.len() {
        let p = primes[i];
        let m = int_sqrt(N/(p*p));
        if m <= p {
            break
        }
        counter += pi[m] - pi[p]
    }
    counter
}

fn main() {
    let N: usize = read();
    println!("{}", F(N))
}