浅谈质数筛法

质数的定义

如果一个整数只有 \(1\) 和它本身这两个因数，那么这个数就是一个质数。

同时，如果一个整数 \(>1\) 且它不是质数，那么我们称这个数是合数。

\(0,1\) 这两个数既不是质数，也不是合数。

1. 试除法

如果给定一个数，判断它是不是质数，那么只判断 \([2,n-1]\) 中的任意一个是否能整除它，如果可以那就是合数，否则是质数。

这里有一个优化：如果 \(n\) 是一个合数，那么 \(n\) 一定包含一个非 \(1\) 的 \(<\sqrt{n}\) 的因数。

证明可以用反证法：如果 \(n\) 是一个合数，且 \(n=p\times q(p,q>\sqrt{n})\) ，因为有 \((\sqrt{n})^2=n\) ，所以 \(p\times q>n\) ，与已知条件矛盾。

代码如下：

inline bool isprime(int n) {
    if (n == 0 || n == 1) return false; //这里记得特判
    for (int i = 2;i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

判断一次的时间复杂度是 \(\mathcal{O}(\sqrt{n})\) ，如果要判断 \([1,n]\) 中有哪一些是质数，那么时间复杂度是 \(\mathcal{O}(n\sqrt{n})\) 。时间复杂度较高。

埃氏筛法

试除法一个一个判断太慢了，我们可以考虑这样做：

对于每一个数 \(x\) ， \(2x,3x,4x,5x\dots\) 一定都不是质数，可以一遍把全部的都筛掉。

也就是说，对于每一个质数（不用管合数的原因是合数的倍数会被质数筛掉），枚举所有小于 \(n\) 的倍数，那些倍数都不是质数。

跟上面试除法一样，不需要从 \(2\) 枚举到 \(n\) ，因为每一个合数一定有一个小于 \(\sqrt{n}\) 的质因子，所以枚举到 \(\sqrt{n}\) 就可以了。

根据这个思路，写出代码：

bool isprime[N];
inline void Prime(int n) {
	memset(isprime ,true ,sizeof(isprime));
    isprime[0] = isprime[1] = false;
    for (int i = 2;i * i <= n; i++)
        if (isprime[i])
            for (int j = 2;j * i <= n; j++)
                isprime[i * j] = false;
}

时间复杂度为 \(\mathcal{O}(\dfrac{n}{2}+\dfrac{n}{3}+\dfrac{n}{5}+\dfrac{7}{2}+\cdots)=\mathcal{O}(n\log\log n)\) 。

线性筛/欧拉筛：

埃氏筛还可以优化：有一些数被多次标记了，比如 \(12\) ，在枚举 \(3\) 的倍数的时候算了一次，在枚举 \(2\) 的倍数的时候也算了一次。

线性筛/欧拉筛优化的思路就是：每次只枚举 \(i\) 的质数倍，同时每一个数字只能被它最小的质因子筛一次。

代码如下：

int prime[N] ,cnt; bool isprime[N];
inline void Prime(int n) {
    memset(isprime ,true ,sizeof(isprime));
    for (int i = 2;i <= n; i++) {
        if (isprime[i]) prime[++cnt] = i;
        //注意这里没有限制只能筛质数的倍数
        for (int j = 1;j <= cnt && prime[j] * i <= n; j++) {
            isprime[prime[j] * i] = false;
            if (i % prime[j] == 0) break;
        }
    }
}

因为每个数字只会被筛一次，所以时间复杂度是 \(\mathcal{O}(n)\) 。

浅谈质数筛法

原文：https://www.cnblogs.com/Dragon-Skies/p/14255751.html