代码实现 C++ 小计突然之间对质因子产生了浓厚的兴趣，他想知道各个数的质因子分布情况。现在他给你两个正整数 p 和 q，希望你能帮他统计从 2 到 p! 的所有数中，有多少个数的所有质因子都大于 q。

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

const int MAXN = 1e6 + 5;

int prime[MAXN], mu[MAXN], cnt;
bool is_prime[MAXN];
vector<int> factor[MAXN];

void init(int n) {
    cnt = 0;
    for (int i = 1; i <= n; ++i) {
        is_prime[i] = true;
        factor[i].clear();
    }
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
            factor[i].push_back(i);
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
            is_prime[i * prime[j]] = false;
            if (i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                factor[i * prime[j]] = factor[i];
                factor[i * prime[j]].push_back(prime[j]);
                break;
            }
            mu[i * prime[j]] = -mu[i];
            factor[i * prime[j]] = factor[i];
            factor[i * prime[j]].push_back(prime[j]);
        }
    }
}

int main() {
    int p, q;
    cin >> p >> q;

    // 预处理 mu 和 factor
    init(p);

    // 计算 A
    int A = 0;
    for (int i = 2; i <= p; ++i) {
        bool flag = true;
        for (int j = 0; j < factor[i].size(); ++j) {
            if (factor[i][j] <= q) {
                flag = false;
                break;
            }
        }
        if (flag) ++A;
    }

    // 计算 B
    vector<int> B(cnt + 1);
    for (int i = q + 1; i <= cnt; ++i) {
        int cur = 0;
        for (int j = i; j <= p; j += i) {
            bool flag = true;
            for (int k = 0; k < factor[j].size(); ++k) {
                if (factor[j][k] <= i) {
                    flag = false;
                    break;
                }
            }
            if (flag) ++cur;
        }
        B[i] = cur;
    }

    // 使用容斥原理计算答案
    int ans = 1;
    for (int i = q + 1; i <= cnt; ++i) {
        if (mu[i]) {
            ans += mu[i] * (B[i] - B[i + 1]);
        }
    }
    cout << ans + p - A - 1 << endl;

    return 0;
}