质数筛法

本文包括埃氏筛和线性筛。

埃氏筛

$\Theta(n\log \log n)$

复杂度证明需要复变函数知识，从略。

void prime()
{
    for (int i = 2; i <= N; i++) {
        if (isp[i]) continue;
        pri[++cnt] = i;
        for (int j = i + i; j <= N; j += i)
            isp[j] = 1;
    }
}

线性筛

$\Theta(n)$

保证了每个合数只被最小质因数筛除一次。

void prime()
{
    for (int i = 2; i <= N; i++) {
        if (!isp[i]) 
            pri[++cnt] = i;
        for (int j = 1; pri[j] * i <= N; j++) {
            isp[pri[j] * i] = 1;
            if (i % pri[j] == 0) break; // 关键代码
        }
    }
}

对关键代码的正确性进行证明。设第二层循环枚举到 $pri_{j0}$ 时，满足 if 的条件。若此时不终止循环，则对于后续枚举到的 $pri_{j1}$，均有等式

$pri_{j1} \cdot i=\frac{i}{pri_{j0}^n}\cdot (pri_{j0}^n\cdot pri_{j_1})$

此时则造成了对同一合数的重复枚举。又因为对等式右边相乘的两数， $\gcd(\frac{i}{pri_{j0}^n},pri_{j0}^n\cdot pri_{j_1})=1$，所以这两个数的组合必然能在 if 跳出循环前出现，得证。