素因数分解（試し割り法）

GitHub last commit

概要

正の整数 $n$ を受け取り，$n$ の素因数を昇順に列挙する．

制約

計算量

実装

// 👇👇👇👇👇👇👇👇👇👇👇👇 number/factorize 👇👇👇👇👇👇👇👇👇👇👇👇
fn factorize(n: u64) -> Vec<u64> {
    assert!(n != 0);
    let mut res = vec![];
    let mut tmp = n;
    for i in (2..).take_while(|&i| i * i <= n) {
        while tmp % i == 0 {
            res.push(i);
            tmp /= i;
        }
    }
    if tmp > 1 {
        res.push(tmp);
    }
    res
}
// 👆👆👆👆👆👆👆👆👆👆👆👆 number/factorize 👆👆👆👆👆👆👆👆👆👆👆👆

Verified with

戻る