质因数分解-试除法

作者: dachengquan | 来源:发表于2020-08-04 19:16 被阅读0次

算数基本定理
任何一个大于1的正整数都能被唯一分解为有限个质数的乘积。 $N=p_1^{c_1}p_2^{c_2}...p_n^{c_n}$
其中 $c_i$ 是正整数， $p_i$ 是质数，且满足 $p_1<p_2<...<p_m$
试除法
结合质数判定的试除法和埃筛，扫描2~ $\sqrt{N}$ 之间的每个整数d,如果d能整除n，则从N中除掉所有的因子d，同时累计除去d的个数。
如果d是合数，那么组成他的因子一定在前面就被除去了，累计的d一定是质数。组成N，大于 $\sqrt N$ 的质数最多有1个，如果存在就是最后剩下的N。

int get_primes(int n){
    for(int i = 2;i<=n/i;i++){
        if(n%i==0){
            int k = 0;
            while(n%i==0){
                k++;
                n/=i;
            }
            cout<<i<<"^"<<k<<endl;
        }
    }
    if(n>1) cout<<n<<"^"<<1<<endl;
    cout<<endl;
}