筛法复习

首先考虑筛素数， 朴素的判断素数复杂度 (O(sqrt n))​

埃氏筛

前几天做 mit6.s081 lab 的时候看到的， 其实就是埃氏筛法

p = get a number from left neighbor
print p
loop:
    n = get a number from left neighbor
    if (p does not divide n)
        send n to right neighbor

正确性是比较显然的，每一次 print 出来的数， 都是经过了比其小的素数的筛选， 说明其没有别的质因数。

for(int i = 2;i < N;i++){
    if(isprime[i]){
      	for(int j = 2 * i;j < N;j += i) isprime[j] = false; // 可以从 i*i 开始枚举
    }
}

调和级数 log 复杂度， 复杂度是 (O(nlogn))

线性筛

void init(){
    for(int i = 2;i < N;i++){
        if(!vis[i]) prime[++cnt] = i;
        for(int j = 1;j <= cnt && prime[j] * i < N;j++){
            vis[i * prime[j]] = 1;
            if(i % prime[j]) break;
        }
    }
}

可以把理解的重点放到 if(i % prime[j]) break; 上

对于每一个数 i​ ， 都会用小于等于其最小质因数的素数 prime[j]​ ，把 i * prime[j] 筛去

对于每一个合数， 都会被其最小质因数筛去， 例如考虑

(n = p_1^{k_1}p_2^{k_2}...p_m^{k_m}) , 它肯定会被 (p_1) 筛去，并且只会被 (p_1)​​ 筛去

考虑它被 (p_2) 筛去， 则 prime[j] = p2 , i = n / p2

在枚举 j 的时候， 枚举到 (p_1) 的时候就 break 出去了，所以不会被 (p_2) 筛去， 其余同理

因而其复杂度是 (O(n))​ ， 是一种很优秀的筛法， 并且是一种筛积性函数的通用筛法