cp_library_rs/number_theory/
factors_all.rs

1//! 高速な約数列挙
2
3/// 約数列挙を行う
4/// - `1 ~ N`までの数の約数を高速に列挙する
5/// - 時間計算量: $`O(N \log\log N)`$
6pub fn factors_all(n: usize) -> Vec<Vec<usize>> {
7    let mut res = vec![vec![]; n + 1];
8    for i in 1..=n {
9        for j in 1.. {
10            if i * j > n {
11                break;
12            }
13            res[i * j].push(i);
14        }
15    }
16    res
17}