线性筛
最初，线性筛只是用来筛质数罢了。。。
void sieve(int n) {
static int v[N], p[N], pr;
// v[i] 表示 i 的最小质因子
// p[N] 和 pr 用来存质数表
for (int i = 2; i <= n; ++i) {
if (v[i] == 0) v[i] = i, p[++pr] = i;
// 没被筛，是质数
for (int j = 1; j <= pr && i*p[j] <= n; ++j) {
v[i*p[j]] = p[j];
if (i % p[j] == 0) break;
// 当 i 是 p[j] 的倍数时 break
}
}
}代码简短，便于记忆。。。
but，为什么复杂度是线性的呢？
- 在筛的过程中，上面的程序将(itimes p[j])的最小质因子定为(p[j])。
- 先不考虑其正确性，将(i)唯一分解，得到(i=p_1^{c_1} times p_2^{c_2} times cdots times p_k^{c_k}（p_1leq p_2 leq cdots leq p_k）)。
- 而此时一定有(p[j]leq p_1)，因为当(p[j]=p_1)时就已经break了。
- 同样由于(p[j]leq p_1)，(i times p[j])的最小质因子显然为(p[j])。
然鹅还是没有证明复杂度是线性的。。。
- 考虑每个数(x)被筛到的原因。
- 若(x)为质数，则(x)被筛是理所当然的。
- 若(x)非质数，则(x)只会被其最小质因子筛到。
所以，每个数会且仅会被筛一次，故时间复杂度为(O(n))。
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
