haar_lib/math/factorize/
trial.rs

1//! 試し割り素因数分解
2
3/// 試し割り素因数分解
4///
5/// **Time comlexity** $\sqrt{n}$
6pub fn factorize(mut n: u64) -> Vec<(u64, usize)> {
7    let mut ret = vec![];
8
9    let mut i = 2;
10    while i * i <= n {
11        if n % i == 0 {
12            let mut c = 0;
13            while n % i == 0 {
14                n /= i;
15                c += 1;
16            }
17            ret.push((i, c));
18        }
19        i += 1
20    }
21
22    if n != 1 {
23        ret.push((n, 1));
24    }
25
26    ret
27}