struct get_primes {
std::vector<int> pr;//获取质数的载体
std::vector<int> st;//标记质数
//构造函数
get_primes(const int N) :st(N, 0) {}
//线性筛主体
std::vector<int> get_p(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) pr.emplace_back(i);
for (int j = 0; pr[j] <= n / i; j++) {
st[pr[j] * i]++;
if (i % pr[j] == 0) break;
}
}
return pr;
}
};
自用