试除法判定质数

暴力做法：枚举 $2$ ~ $n-1$ 的所有数，判断能否将 $n$ 整除，如果存在一个数能把 $n$ 整数，说明 $n$ 不是质数

实际上只需要枚举到 $\sqrt{n}$ 即可，如果 $a$ 是 $n$ 的约数，那么 $\frac{n}{a}$ 也是 $n$ 的约数，我们只需要检验 $min(a,\frac{n}{a})$ 即可

bool is_prime(int x){
    if (x == 1) return 0;//1不是质数
    for (long long i = 2; i <= sqrt(x); i++)//从小到大枚举
        if (x % i == 0) return 0;//如果能整除，立即返回非质数
    return 1;//返回是质数
}

具体的计算中，i <= sqrt(x) 的操作可以优化为 i * i <= x 或 i <= x / i ，得到常数级的优化

不难看出对于判断 $n$ 而言，试除法判断质数的时间复杂度为 $O(\sqrt{n})$

埃拉托斯特尼筛法

这是一种在给定区间内有效筛选素数的方式，原理是：

  • 从 $2$ 开始枚举每一个数，直到到达给定的界限
  • 对每一个枚举的数都判断一次状态
  • 枚举当前质数的倍数，他们必然是合数，更改状态

最后每个数都存在一个状态，要么被标记为合数，要么被标记为质数，这就完成了筛选素数的过程

bool st[N];//状态数组，合数被标记为 1，初始化时都为 0
int prime_mem[N];//记录素数
int cnt;//素数个数

void Eratosthens(int n){
    for (long long i = 2; i <= n; i++){//从小到大枚举
        if (!st[i]){//如果这个数是素数
            prime_mem[++cnt] = i;//素数个数加 1，并记录
            for (long long j = i * i; j <= n; j += i)//从小到大枚举素数的倍数
                st[j] = 1;//标记素数
        }
    }
}

其中 for (long long j = i * i; j <= n; j += i) 从 i * i 开始标记合数，这是因为小于 i * i 的合数在之前已经被标记过了

证明如下：

  • 设 $k < i\quad k\in N^+$，则 $ki $ 为 $i$ 的倍数，满足 $ki<i^2$

$$ ki<i^2 \iff k<i $$

  • 存在质数$p$， $p<i$，$p$ 标记了它的倍数 $kp$ ，就有

$$ p\times k=p \iff k=1 $$

  • 由于 $k<i$ ，所以下述不等式成立

$$ p\times k<p\times i<i^2 \iff p<i,k<i $$

所以任意的小于 $i^2$ 的合数，都已经被小于 $i$ 的一个素数 $p$ 标记过

显然，根据算数基本定理，要找到 $n$ 以内的所有质数，只需要对不超过 $\sqrt{n}$ 的素数进行筛除即可

for (long long i = 2; i <= n; i++) $\rightarrow$ for (long long i = 2; i * i <= n; i++)

这种筛法的时间复杂度在 $O(n\log\log n)$ ，近乎于 $O(n)$

线性筛法/欧拉筛法

对于上面的埃拉托斯特尼筛法，过程中会对一个合数重复标记多次，通过线性筛法，可以做到让一个合数只被标记一次

那么时间复杂度就能降到 $O(n)$

原理如下：

  • 合数总是可以分解为多个质数的积，（整数惟一分解定理）
  • 使筛掉的方法唯一，每次通过合数的最小质因子筛掉
bool st[N];//状态数组，合数被标记为 1，初始化时都为 0
int prime_mem[N];//记录素数
int cnt;//素数个数

void Euler(int n){
    for (long long i = 2; i <= n; i++){
        if (!st[i]) prime_mem[++cnt] = i;
        for (long long j = 1; i * prime_mem[j] <= n; j++){
            st[i * prime_mem[j]] = 1;
            if (i % prime_mem[j] == 0) break;//保证只被最小质因子筛除
        }
    }
}

$i$ 为质数，最多枚举到自身中断，即 $i^2\ \%\ i=0$ 。$i$ 为合数，最多枚举到最小质因子 $p$ 结束，即 $i*p\ \%\ i=0$

其中的 st[i * prime_mem[j]] = 1; 做到了具体的筛除过程