请生成线性筛求约数个数的c++代码

以下是使用线性筛求约数个数的 C++ 代码：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1000000;

vector<int> primes; // 存储素数
int factor[MAXN + 1]; // 存储最小素因子

void linear_sieve() {
    for (int i = 2; i <= MAXN; i++) {
        if (factor[i] == 0) {
            factor[i] = i; // i 是素数
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && primes[j] <= factor[i] && i * primes[j] <= MAXN; j++) {
            factor[i * primes[j]] = primes[j];
        }
    }
}

int count_divisors(int n) {
    int cnt = 1;
    for (int i = 0; i < primes.size() && primes[i] * primes[i] <= n; i++) {
        int p = primes[i], e = 0;
        while (n % p == 0) {
            n /= p;
            e++;
        }
        cnt *= e + 1;
    }
    if (n > 1) cnt *= 2;
    return cnt;
}

int main() {
    linear_sieve();
    int n;
    cin >> n;
    cout << count_divisors(n) << endl;
    return 0;
}

该程序先使用线性筛法得到 $1$ 到 $10^6$ 之间的素数，同时记录每个数的最小素因子。接着通过遍历素数，统计 $n$ 的约数个数。具体地，设 $n = \prod_{i=1}^k p_i^{e_i}$ 是 $n$ 的质因数分解式，则 $n$ 的约数个数为 $\prod_{i=1}^k (e_i + 1)$。注意当 $n$ 的质因子中存在大于 $\sqrt{n}$ 的数时，还需要再乘以 $2$。