质数

试除法判定质数

bool is_prime(int x)
{
    if (x < 2)
        return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0)
            return false;
    return true;
}

质数的筛选

给定一个整数$N$，求出$1$到$N$间的所有质数，称为质数的筛选问题

最基础埃氏筛

埃氏筛基于思想：任意整数的倍数都不是质数。因此可以从$2$开始，从小到大扫描每个数$x$，把它的倍数都打上标记。若扫描到一个数$x$时，这个数没有被标记，那么说明这个数是质数(从$2$到$x-1$没有数能整除$x$)。

void primes(int n)
{
    memset(st, false, sizeof st); //合数标记
    for (int i = 2; i <= n; i++)
    {
        if (st[i])
            continue;
        for (int j = 2; j <= n / i; j++)
            st[i * j] = true;
    }
}

优化埃氏筛

对于基础埃氏筛，一些数会重复打上标记，例如$2$和$3$都会把$6$打上标记。实际上，小于$x^2$的$x$的倍数在扫描更小的数时就已经被标记过了。想不通的可以就看一下$6$这个数，$6$是$3$的$2$倍因此会在扫描$3$时又被标记，$3$的$2$倍等价于$2$的$3$倍，而这在扫描$2$时就被标记了。时间复杂度是$O(NloglogN)$

void primes(int n)
{
    memset(st, false, sizeof st); //合数标记
    for (int i = 2; i <= n; i++)
    {
        if (st[i])
            continue;
        for (int j = i; j <= n / i; j++)
            st[i * j] = true;
    }
}

线性筛

即使是优化的埃氏筛还是会重复标记一些数，例如$12$还是会被$2$和$3$重复标记。线性筛的思想是让每个合数只被它的最小质因子筛一次。设数组$v$记录每个数的最小质因子，我们按照一下步骤维护$v$：
1.依次考虑$2$~$n$的每一个数
2.若$v[i]=i$，说明$i$是质数，把它保存下来
3.扫描不大于$v[i]$的每个质数$p$，令$v[i\times p]=p$。也就是在$i$的基础上累积一个质因子$p$。因为$p\leq v[i]$，所以$p$就是合数$i\times p$的最小质因子。
每个合数只会被最小质因子筛一次，时间复杂度是线性$O(N)$

// v[i]!=i就说明i是合数，知道这个好像更好理解一点
void primes(int n)
{
    memset(v, 0, sizeof v); // v[i]记录数字i的最小质因子
    m = 0;                  // m记录质数个数
    for (int i = 2; i <= n; i++)
    {
        if (v[i] == 0) // i是质数
        {
            v[i] = i;
            prime[++m] = i;
        }
        for (int j = 1; j <= m; j++)
        {
            //若i有比prime[j]更小的质因子，或超出n的范围，则停止循环
            if (prime[j] > v[i] || prime[j] > n / i)
                break;
            // prime[j]是合数i*prime[j]的最小质因子
            v[i * prime[j]] = prime[j];
        }
    }
}

质因数分解

算术基本定理

任何一个大于$1$的正整数都能唯一分解成有限个质数的乘积，可写作：$N={p_1}^{c_1}{p_2}^{c_2}\cdots {p_m}^{c_m}$
其中$c_i$都是正整数，$p_i$都是质数，且$p_1<p_2<\cdots <p_m$

试除法分解质因数

扫描$2$~$\sqrt n$的每个数$d$，若$d$能整除$N$，则从$N$中除掉所有的因子$d$，同时记录除去的$d$的个数
特别地，若没有$2$~$\sqrt n$的数能整除$n$，说明$n$是质数无需分解

void divide(int n)
{
    m = 0;
    for (int i = 2; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            p[++m] = i, c[m] = 0;
            while (n % i == 0)
                n /= i, c[m]++;
        }
    }
    if (n > 1) //还除剩一个质数
        p[++m] = n, c[m] = 1;
}

质数相关题有： 质数距离 阶乘分解