cp_library_rs/number_theory/
factorize.rs

1//! 素因数分解
2
3/// 非負整数 $`n`$ を素因数分解し、`素因数`のベクタを返す
4/// - 計算量 : $`O(\sqrt{n})`$
5pub fn factorize_vec(mut n: usize) -> Vec<usize> {
6    let mut res = Vec::new();
7    for i in 2.. {
8        if i * i > n {
9            break;
10        }
11        while n % i == 0 {
12            n /= i;
13            res.push(i);
14        }
15    }
16    if n > 1 {
17        res.push(n);
18    }
19    res
20}
21
22/// 非負整数 $`n`$ を素因数分解し、`(素因数,指数)`のベクタを返す
23/// - 計算量 : $`O(\sqrt{n})`$
24pub fn factorize_pairs(mut n: usize) -> Vec<(usize, usize)> {
25    let mut res = Vec::new();
26    for i in 2.. {
27        if i * i > n {
28            break;
29        }
30        let mut cnt = 0;
31        while n % i == 0 {
32            n /= i;
33            cnt += 1;
34        }
35        if cnt >= 1 {
36            res.push((i, cnt));
37        }
38    }
39    if n > 1 {
40        res.push((n, 1));
41    }
42    res
43}