求约数

求n的正约数集合（试除法）

原理

见《进阶指南》第139页。

代码

const int N = 100010;
int idx, factors[N];

void get_factors (int x) {
    for (int i = 1; i <= x / i; ++ i) {
        if (x % i == 0) {
            factors[++ idx] = i;
            if (i != n / i) factors[++ idx] = n / i;
        }
    }
}

求1 ~ n每个数的正约数集合（倍数法）

原理

见《进阶指南》第140页。

代码

const int N = 100010;
vector<int> factors[N];

void get_factors (int n) {
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n / i; ++ j)
            factors[i * j].push_back(i);
}