质数
质数和合数是针对所有大于 11 的「自然数」来定义的（所有小于等于 11 的数都不是质数）。

所有小于等于 11 的整数既不是质数也不是合数。

质数的判定——试除法：

d|nd|n 代表的含义是 dd 能整除 nn。（这里的 | 代表整除）

一个合数的约数总是成对出现的，如果 d|nd|n，那么 (n/d)|n(n/d)|n，因此我们判断一个数是否为质数的时候，只需要判断较小的那一个数能否整除 nn 就行了，即只需枚举 d≤(n÷d)d≤(n÷d)，即 d×d≤nd×d≤n，d≤n√d≤n 就行了。

sqrt(n) 这个函数执行的时候比较慢。

bool is_prime(int x)
{
    if(x < 2) return false;
    for(int i = 2; i <= x / i; i ++) // x / i 是最快且最不容易爆炸的写法
    {
        if(x % i == 0) return false;
    }
    return true;
}

分解质因数——试除法（算数基本定理）

算数基本定理：任何一个大于 11 的自然数 nn，如果 nn 不为质数，那么 nn 可以唯一分解成有限个质数的乘积 n=Pa11Pa22Pa33…Pannn=P1a1P2a2P3a3…Pnan，这里 P1<P2<P3<⋯<PnP1<P2<P3<⋯<Pn 均为质数，其中指数 aiai 是正整数。

特别要注意——分解质因数与质因数不一样，分解质因数是一个过程，而质因数是一个数。

一个合数分解而成的质因数最多只包含一个大于 n√n 的质因数。（反证法，若 nn 可以被分解成两个大于 n√n 的质因数，则这两个质因数相乘的结果大于 nn，与事实矛盾）

当枚举到某一个数 ii 的时候，nn 的因子里面已经不包含 [2,i−1][2,i−1] 里面的数（已经被除干净了），如果 n|in|i，则 ii 的因子里面也已经不包含 [2,i−1][2,i−1] 里面的数，因此每次枚举的数都是质数。

质因子（质因数）在数论里是指能整除给定正整数的质数。根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。

两个没有共同质因子的正整数称为互质。因为 11 没有质因子，11 与任何正整数（包括 11 本身）都是互质。

只有一个质因子的正整数为质数。

void divide(int x)
{
    for(int i = 2; i <= x / i; i ++)
    {
        if(x % i == 0)
        {
            int s = 0;
            while(x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    }
    if (x > 1) cout << x << ' ' << 1 << endl; // 大于sqrt(n)的数
    cout << endl;
}

筛质数（朴素筛法）

步骤：把 [2,n−1][2,n−1] 中的所有的数的倍数都标记上，最后没有被标记的数就是质数。

原理：假定有一个数 pp 未被 [2,p−1][2,p−1] 中的数标记过，那么说明，不存在 [2,p−1][2,p−1] 中的任何一个数的倍数是 pp，也就是说 [2,p−1][2,p−1] 中不存在 pp 的约数，因此，根据质数的定义可知：pp 是质数。

调和级数：当 nn 趋近于正无穷的时候，12+13+14+15+⋯+1n=lnn+c12+13+14+15+⋯+1n=ln⁡n+c（cc 是欧拉常数，约等于 0.5770.577 左右）

时间复杂度：约为 O(nlogn)O(nlog⁡n)（注：此处的 loglog 特指以 22 为底）

埃氏筛（稍加优化版的筛法）

质数定理：1∼n1∼n 中有 nlnnnln⁡n个质数。

步骤：在朴素筛法的过程中只用质数项去筛。

时间复杂度：O(nlog(logn))O(nlog⁡(log⁡n))。

int primes[N], cnt; // primes[] 存储所有素数
bool st[N]; // st[x] 存储 x 是否被筛掉

void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(st[i]) continue;
        primes[cnt ++] = i;
        for(int j = i + i; j <= n; j += i) st[j] = true;
    }
}

线性筛

若 n≈106n≈106，线性筛和埃氏筛的时间效率差不多，若 n≈107n≈107，线性筛会比埃氏筛快了大概一倍。

核心：1∼n1∼n 内的合数 pp 只会被其最小质因子筛掉。（算数基本定理）

原理：1∼n1∼n 之内的任何一个合数一定会被筛掉，而且筛的时候只用最小质因子来筛，然后每一个数都只有一个最小质因子，因此每个数都只会被筛一次，因此线性筛法是线性的。

枚举到 ii 的最小质因子的时候就会停下来，即 if(i % primes[j] == 0) break;

当 i % primes[j] != 0 时，primes[j] 一定小于 ii 的最小质因子，primes[j] 一定是 primes[j]i 的最小质因子。
当 i % primes[j] == 0 时，primes[j] 一定是 ii 的最小质因子，而 primes[j] 又是 primes[j] 的最小质因子，因此 primes[j] 是 primes[j]i 的最小质因子。

int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[cnt ++] = i;
        // j < cnt 不必要，因为 primes[cnt - 1] = 当前最大质数
        // 如果 i 不是质数，肯定会在中间就 break 掉
        // 如果 i 是质数，那么 primes[cnt - 1] = i，也保证了 j < cnt
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

作者：yxc
链接：https://www.acwing.com/video/27/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处