数论基础——质数

试除法判定质数

首先，我们要知道什么是质数。质数，又称素数，只有两个正因数(1和它本身)的自然数即为质数。这里要注意一点：1不是质数。那么如果要判断一个数是否是质数，我们就可以判断一个数是否存在除了1和它本身的以外的其他的正因数。关键代码如下：

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

上述代码的时间复杂度是$O(n)$。我们再进一步思考，如果i (i<x)是x的因数，那么x/i也是x的因数。 这说明，一个自然数的因数是成对出现的。由于我们是判断一个数是否是质数，我们并不需要枚举该自然数所有的因数，所以我们只枚举较小的因数即可，那么上述代码的for循环中 i<x就可以写为i<x/i 。考虑到sqrt(x)是可能是整数，那么就i<x/i就更新为i<=x/i。
优化后的代码如下：

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

此代码的时间复杂度是$O(\sqrt n)$。

注意事项

i<=x/i不可以写成i*i<=x，这是因为如果i很大的话，i*i会爆int。

分解质因数

上面我提到了质数的定义。那么分解质因数指的是将一个数k进行因式分解，分解出来的每一个因数都是质数，都是不可再分的。那么这样的话，在分解的过程中可能会出现若干个相同的质因数，比如8，有三个相同的质因数2。所以分解质因数的基本思想就是从最小的质数开始遍历所有的数，一旦出现一个数i是k的因数，那么我们就将i从k中全部剔除干净。关键代码如下：

void divPrimes(int x){
    for(int i=2;i<=x;++i){ //如果x是质数的话，最后分解下来就只有它本身
        if(x%i == 0){
            int s = 0;
            while(x%i==0){
                s++;
                x/=i;
            }
            cout<<i<<' '<<s<<endl;
        }
    }
}

最坏的情况是x为质数，那么它的时间复杂度上限是$O(n)$。我们可以尝试着优化一下这个代码。
通过观察，我们发现，任何一个数n最多只有一个大于$\sqrt n$的质因数。

证明(反证法):假如数n至少有大于等于2个大于$\sqrt n$的质因数，那么这些质因数的乘积一定大于n,与前提矛盾，命题得证。

所以，我们可以在循环体中做如下优化：

void divPrimes(int n){
    for(int i=2;i<=n/i;++i){
        if(n%i == 0){
            int s=0;
            while(n%i==0){
                n/=i;
                ++s;
            }
            cout<<s<<' '<<i<<endl;
        }
    }
    if(n>1) cout<< n << ' '<< 1;//因为质因数可能大于sqrt(n),所以我们需要特判一下。
}

可能存在的疑问

有的同学可能会有这样的疑惑：我们不是分解质因数吗？那么我们应该遍历所有的质数才对啊，怎么会遍历所有的数呢？我们怎么能确定因数一定是质数呢？
回答：这个就涉及到了算数基本定理。

算数基本定理，又称为质因数分解定理，它是这样说的：任何一个大于1的整数n都可以分解成若干个质因数的连乘积，如果不计各个质因数的顺序，那么这种分解是惟一的，即$n = p_1^{\alpha _1} p_2^{\alpha _2} p_3^{\alpha _3} \ldots p_k^{\alpha _k}$,其中，$p_1<p_2<p_3<\ldots<p_k$,$\alpha _i$表示质因数出现的次数。

这个定理也变相地说明了一个数的最小因数一定是质数。

现在我们来证明上面那句话(当然不是证明算数基本定理，毕竟我不会证)。
证明(反证法)：假如一个数的最小因数不是质数，那么说明它一定是合数。而合数是可以再分解成两个更小的数，所以与我们的假设矛盾，命题得证！

再回到原问题上，由于一个数的最小因数一定是质数，那么我们对一个数n进行质因数分解时遍历到的第一个因数就一定是质数。之后我们就把这个质因数从原数n中全部剔除掉，得到一个新的数m，m里不包含我们之前遍历到的质因数。这个新的数m的最小质因数也是质数，如此循环，我们可以保证所有的因数一定是质数。