エラトステネスの篩

[tipstar0125]

https://qiita.com/drken/items/3beb679e54266f20ab63

計算量：

• N個の高速素因数分解O(NlogN)

高度合成数：https://algo-method.com/descriptions/92

• 1e9以下の最大の高度合成数は、735134400 で、約数は 1344 個
• 1e18以下の最大の高度合成数は、897612484786617600 で、約数は 103680 個

問題：

• https://atcoder.jp/contests/abc177/tasks/abc177_e

[tipstar0125]

#[derive(Debug, Clone, Default)]
struct Eratosthenes {
    is_prime: Vec<bool>,
    min_factor: Vec<isize>,
    mobius: Vec<isize>,
}

impl Eratosthenes {
    fn new(n: usize) -> Self {
        let mut is_prime = vec![true; n + 1];
        let mut min_factor = vec![-1; n + 1];
        let mut mobius = vec![1; n + 1];
        is_prime[0] = false;
        is_prime[1] = false;
        min_factor[1] = 1;

        for p in 2..=n {
            if !is_prime[p] {
                continue;
            }
            min_factor[p] = p as isize;
            mobius[p] = -1;

            let mut q = p * 2;
            while q <= n {
                is_prime[q] = false;
                if min_factor[q] == -1 {
                    min_factor[q] = p as isize;
                }
                if (q / p) % p == 0 {
                    mobius[q] = 0;
                } else {
                    mobius[q] = -mobius[q];
                }
                q += p;
            }
        }
        Eratosthenes {
            is_prime,
            min_factor,
            mobius,
        }
    }
    fn factorize(&self, N: usize) -> Vec<(usize, usize)> {
        let mut ret = vec![];
        let mut n = N;
        while n > 1 {
            let p = self.min_factor[n];
            let mut exp = 0;

            while self.min_factor[n] == p {
                n /= p as usize;
                exp += 1;
            }
            ret.push((p as usize, exp));
        }
        ret
    }
    fn dividers(&self, N: usize) -> Vec<usize> {
        let mut ret = vec![1];
        let pf = self.factorize(N);
        for &(p, exp) in &pf {
            let m = ret.len();
            for i in 0..m {
                let mut v = 1;
                for _ in 0..exp {
                    v *= p;
                    ret.push(ret[i] * v);
                }
            }
        }
        ret.sort();
        ret
    }
}