1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//! 高速な約数列挙

/// 約数列挙を行う
/// - `1 ~ N`までの数の約数を高速に列挙する
/// - 時間計算量: $`O(N \log\log N)`$
pub fn factors_all(n: usize) -> Vec<Vec<usize>> {
    let mut res = vec![vec![]; n + 1];
    for i in 1..=n {
        for j in 1.. {
            if i * j > n {
                break;
            }
            res[i * j].push(i);
        }
    }
    res
}