筛法

埃拉托斯特尼筛法

考虑这样一件事情：对于任意一个大于 $1$ 的正整数 $n$，那么它的 $x$ 倍就是合数 $(x>1)$。利用这个结论，我们可以避免很多次不必要的检测。

如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。

$O\left({\sum }_{k=1}^{\pi (n)}\frac{n}{p_k}\right)=O\left(n{\sum }_{k=1}^{\pi (n)}\frac{1}{p_k}\right)=O(n\log \log n)$

void eratosthenes(int n) {
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[1] = false;
    for (int i = 2; i <= n; i++)
        if (isPrime[i]) {
            Prime[cnt++] = i;
            for (int j = 2 * i; j <= n; j += i)
                isPrime[j] = false;
        }
}

线性筛法

埃氏筛法仍有优化空间，它会将一个合数重复多次标记。如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 $O(n)$ 了。

void eulerSieve(int n) {
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i])
            prime[cnt++] = i;
        for (int j = 0; j < cnt && (long long)i * prime[j] <= n; j++) {
            isPrime[i * prime[j]] = false;
            if (i % prime[j] == 0)
                break;
        }
    }
}

在线性筛中，每一个合数 $y$ 都是被最小的质因子 $p$ 筛掉。

当出现 $p_j\mid i$ 时，如果继续循环筛下去，$y=i\cdot p_{j+1}=(\frac{i}{p_j}{p}_{j+1})\cdot p_j$ 会被筛两次；

我们选择 $(\frac{i}{p_j}{p}_{j+1})\cdot p_j$ 来筛，使得每个数只被筛一次。

例如，$p_j=2，p_{j+1}=3，i=4$

$12=4\times 3=(\frac{4}{2}\times 3)\times 2=6\times 2$

graph LR
2-->|2|4
3-->|2|6
3-->|3|9
4-->|2|8
5-->|2|10
5-->|3|15
6-->|2|12
7-->|2|14
8-->|2|16
9-->|2|18
10-->|2|20
11
13
17
19