模板
struct Primes {
std::vector<int> pr, p;
size_t sz;
void init(int n) {
p.resize(n + 1, 0); sz = 0; p[1] = 1;
for (int i = 2; i <= n; i++) {
if (!p[i]) {
p[i] = i; pr.emplace_back(i); sz++;
}
for (int j = 0; j < sz && 1LL * pr[j] * i <= n; j++) {
p[i * pr[j]] = pr[j];
if (p[i] == p[j]) break;
}
}
}
size_t size() const {
return sz;
}
int& operator[](size_t i) {
if (i >= sz) return pr[0];
return pr[i];
}
};
使用
初始化
使用init(n)来进行 \(1\) 到 \(n\) 的线性筛
访问数据
重构了[], 可以通过下标访问, 下标从 \(0\) 开始，范围\([0, sz)\)。
pr 存储素数。
p 存储每个数的最小素因子。
