1. 试除法判断质数$O(nlogn)$

因为质数只能被$1$和自己整除，所以只需判断$n$不能被$2$到$\sqrt{n}$的所有数整除即可
代码

2. 筛质数$O(nlogn)$

筛法可行的原因：用每个质数去将它的所有倍数都筛掉，保证所有加进$primes$的都是质数。在筛的过程中后面一定不会枚举到合数，因为根据算术基本定理，这个合数一定可以被前面的质数筛掉。

① 朴素筛法

朴素筛法不管是合数都是质数，都要拿来筛除它的倍数。

void get_primes(){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt ++]=i;  // 把素数存起来
        for(int j = i; j <= n; j += i){  // 不管是合数还是质数，都用来筛掉后面它的倍数
            st[j] = true;
        }
    }
}

② 埃式筛法 $O(nloglogn)$

埃式筛法只是改变了用来筛的元素，因为每个合数都会被比它小的质数筛掉，因此可以只在往$primes$数组中加质数的时候同时用这个元素来筛掉所有它的倍数。

void get_primes(){
    for(int i = 2;i <= n;i ++){
        if(!st[i]){
            primes[cnt ++]=i;
            for(int j = i; j <= n; j += i) st[j]=true;//可以用质数就把所有的合数都筛掉；
        }
    }
}

③ 线性筛法

(1) 每个数$i$*$primes[j]$只会被最小质因数筛一次
1° $i$%$primes[j]$=$0$时，因为我们是从小到大枚举质因子，所以第一个满足$i$%$primes[j]$=$0$的$primes[j]$一定是$i$的最小质因子，同理也是$i*primes[j]$的最小质因子

2° $i$%$primes[j]$=$t$≠$0$时，说明还没枚举到$i$%$primes[j]$=$0$，即还没枚举到$i$的最小质因子，所以$primes[j]$就是$i*primes[j]$的最小质因子
(2) 保证所有的合数都会被筛掉

对于一个合数$x$，假设$primes[j]$是$x$的最小质因子，当$i$枚举到$x$/$primes[j]$一定会被筛除，即不会有枚举到$x$的机会。因此可以保证所有合数都会被筛掉。
综上，(1)+(2)可以说明每一个合数都只会被自己的最小质因数筛一次，所以是线性的。

void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        //假设primes[0]为n最小的质因子,i为最大的因数，
        //易知若primes[i]中i>0,则会进入循环后产生多余的标记。
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            //标记;primes[j]一定是primes[j]*i的最小质因子
            st[primes[j]*i] = true;
            //表明primes[j]一定是i的最小质因子,没有必要再遍历,primes要小于等于i的最小质因子
            //这样能保证每个数遍历一遍,而没有重复
            if(i % primes[j] == 0) break;
        }
    }
}

3. 分解质因数

分解质因数就不能用上面筛法的优化了，因为$1$~$n$的数$x$满足是质数但不一定是n的质因数。分解质因数是利用算术基本定理，每找到一个质因数$P_i$，同样要将它的所有倍数(合数)全部筛掉(这里表现为将$n$中所有$P_i$都除掉，因为只用分解因数，不用记录)，这样才能保证每个枚举到的$i$都是质数

枚举可能的质因数的时候只用枚举$2$~$\sqrt{x}$，因为最多有一个大于$\sqrt{x}$的质因数(如果有两个，那么这两个质因数的乘积就大于$x$了，不存在这种分解法)

void divide(int x){
    for (int i = 2; i <= x / i; i ++){
        if(x % i == 0){
            int res = 0;  // 统计这个质因数的个数
            while(x % i == 0) res ++, x /= i;  // 将质数i的所有倍数全部筛除
            printf("%d %d\n", i, res);
        }
    }
    if(x > 1) printf("%d %d\n", x, 1);
    puts("");
}

$eg:$

分解质因数-第$44$场周赛$C$题

区分分解质因数与筛质数

筛质数是通过用前面已经确定的质数将后面更大的合数筛掉，以达到求出$1$~$n$中所有质数的目的
分解质因数只是通过算术基本定理将数$n$分解出式中所有质因数
所以筛质数$i$要从$2$枚举到$n$，而分解质因数只需要从$2$枚举到$\sqrt{n}$