筛质数及其应用

本来想把筛质数写到数论基础——质数( https://www.acwing.com/blog/content/17328/ )那一章，但是筛质数有一个应用——欧拉函数。为了把筛法求欧拉函数说得更加明白，我决定把它们放到同一章节。

筛质数

基本思想
利用质数的定义来筛。具体而言，从小到大遍历每一个数，把当前数的倍数筛掉。如果遍历到某一个数字，它没有被前面所有数的倍数筛掉，那么它就是一个质数。

数据结构
1. 需要一个表示数据是否被筛过的状态数组
2. 需要一个用来存储质数的数组

筛质数共有三种算法，每一种算法都是对前面算法的优化。

暴力做法

具体而言，根据定义写代码

for(int i=2;i<=n;++i){
    if(!st[i]) prime[cnt++] = i;
    for(int j=2;j<=n/i;++j){
        st[j*i] = true;
    }
}

优点
1. 代码简单明了

缺点
1. 同一个数字可能会被多次筛掉
2. 对筛掉的数进行操作，

这些缺点使得代码进行了多次无效运算，增加了算法的时间复杂度。

埃氏筛法

针对于暴力做法中第二个缺点进行优化，即如果当前数已经被筛掉了，我们就跳过本轮循环，不对这个数进行任何操作。换句话说，埃氏筛法是利用质数来筛掉所有的合数。
具体代码实现如下：

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

优点
1. 相比于暴力做法，本算法不会对被筛掉的数进行操作，一定程度上降低了算法复杂度

缺点
1. 同一个数字可能会被多次筛掉。如6，既是2的倍数，也是3的倍数，所以它会被2和3筛掉。

线性筛法

我们对埃氏筛法进一步优化，得到线性筛法。所谓线性，指的是每一个数只会被筛一次。该算法利用一个数的最小质因数把该数筛掉。
具体代码如下：

for(int i=2;i<=x;++i){
    if(!st[i]) prime[cnt++] = i;//如果当前数没有被筛掉，那么它就是质数
    for(int j = 0;prime[j] <= x/i; ++ j){//利用质数的倍数来筛掉合数
    /*
     * 这几步代码是怎么避免埃氏筛法的缺点的？
     * 由于i是不断增加的，而x不变，那么结束该循环时的j一次比一次小
     * 比如6，它首先会被2筛掉,具体而言，在当前数是3,即i = 3时，prime[0] * i = 2 * 3 = 6,st[6] = true;
     * 质数3要想筛掉6，i必须等于2。然而i是不断递增的，所以质数3永远筛不掉6。
     * 总结一下，若一个合数n是两个质数p和q的乘积(p < q)，即n = p * q,那么p筛掉n的条件是当前数i = q,由于q > p,所以p
     * 可以筛掉n；q筛掉n的条件是当前数i = p,由于q > p，那么当前数无论如何都不可能是p，故q永远筛不掉n。
     * 简而言之，合数一定是被它的最小质因数筛掉的。
    */
        st[i * prime[j]] = true;
        if(i % prime[j] == 0){
        //这一步保证了该数是被它的最小质因数筛掉的
        //同时也保证了数组不会发生溢出。如果i是一个质数的话，那么直到把prime数组全部遍历完成，才会跳出循环
            break;
        }
    }
}

筛质数的应用——欧拉函数

欧拉函数
对于正整数$n$，欧拉函数$\phi(n)$指的是在$1\sim n$中与n互质的正整数的个数。
由算数基本定理，若$n = p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_m^{\alpha_m}$，
那么数$n$的计算公式如下：$\phi(n) = n * \frac{p_1 - 1}{p_1} \frac{p_2 - 1}{p_2} \cdots \frac{p_m - 1}{p_m}$

若要求解$n$个数的欧拉函数，当n较小的时候，我们可以直接利用欧拉函数的计算公式来求；当n很大的时候，我们可以利用线性筛质数的方法来求解这n个数的欧拉函数。

计算公式求解欧拉函数

从欧拉函数的计算公式可以看出，我们需要对数$n$进行质因数分解，然后再利用公式求解。
具体代码如下：

int phi(int x){
    int res = x;
    for(int i=2;i<=x/i;++i){
        if(x%i==0){
            res = res / i * (i - 1);
            while(x%i==0){
                x/=i;
            }
        }
    }
    if(x > 1) res = res / x * (x - 1);
    return res;
}

线性筛法求解欧拉函数

我们需要额外定义一个数组phi[N]用来存放数i的欧拉函数值。
已知$phi[i] = i \times \frac{p_1 - 1}{p_1} \frac{p_2 - 1}{p_2} \cdots \frac{p_m - 1}{p_m}$,
若$i \% prime[j] = 0$，说明$prime[j]$是$i$和$i * prime[j]$的最小质因数，
那么$phi[ i * prime[j] ] = i \times prime[j] \times \frac{p_1 - 1}{p_1} \frac{p_2 - 1}{p_2} \cdots \frac{p_m - 1}{p_m}$；
反之，说明$prime[j]$仅是$i * prime[j]$的最小质因数，
$phi[ i * prime[j] ] = i \times prime[j] \times \frac{p_1 - 1}{p_1} \frac{p_2 - 1}{p_2} \cdots \frac{p_m - 1}{p_m} \frac{prime[j] - 1}{prime[j]} = i \times (prime[j]-1) \times \frac{p_1 - 1}{p_1} \frac{p_2 - 1}{p_2} \cdots \frac{p_m - 1}{p_m}$

具体代码如下：

void Phi(int x){
    phi[1] = 1;
    for(int i=2;i<=x;++i){
        if(!st[i]) prime[cnt++] = i,phi[i] = i-1;//质数i的欧拉函数值是i-1
        for(int j = 0;prime[j] <= x/i;++i){
            int t = i * prime[j];
            st[t] = true;
            if(i%prime[j] == 0){
                phi[t] = prime[j] * phi[i];
                break;
            }
            phi[t] = (prime[j] - 1) * phi[i];
        }
    }
}