分解质因数--试除法

2023/5/28 18:23:17

编程Tag： OI

本文主要是介绍分解质因数--试除法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

void divide(int n){
    
    for(int i=2;i<=n;i++) //这个地方是枚举到n 

    {
        if(n%i==0)
        {
            int s=0;
            while(n%i==0)
            {
                n/=i;
                s++;
            }
        cout<<i<<" "<<s<<endl;
        }
    }
    if(n>1)  cout<<n<<" "<<1<<endl;
    cout<<endl;
}
int main()
{
    int n;
    cin>>n;
    
    while (n -- ){
        int x;
        cin>>x;
        
        divide(x);
    }
    
    return 0;

}

但是按照题意我们需要的是枚举质因数，然后呢我们枚举的是 1到n ，这个时候我们就会考虑一个问题，就是1到n这个里面就是不只有质数，还有合数，这个是我们担心的一个问题.

我们来说明一下这个情况

为什么我们枚举这个1-n是可以行的

.............................................................................

比如呢，1-n中有一个合数6，12，8，14

对于6 ,等到枚举到6的时候，其实在2这个质因数的时候就已经有了1次了，在3这个质因数的时候就也有1次了。。。

对于12 ,等到枚举到12的时候，其实在2这个质因数的时候就已经有了2次了，在3这个质因数的时候就也有1次了。。。

对于8,等到枚举到8的时候，其实在2这个质因数的时候就已经有了3次了。。。

对于14 ,等到枚举到14的时候，其实在2这个质因数的时候就已经有了1次了，在7这个质因数的时候就也有1次了。。。

................................................................................

综上所述，可想而知，在这个枚举的过程的时候是不可能枚举到合数的（也不是在枚举不到合数，就在枚举到合数的时候，就会跳过，因为这个合数在之前除他的质因数的时候就已经除干净了）---------eg： 6/3/2=1

..................................................................................

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

void divide(int n){
    
    for(int i=2;i<=n/i;i++)   //如果枚举到n的话时间复杂度就是O（n）的
    
    //但是我们需要优化   ---根据 性质：n中最多包含一个大于sqrt(n)的质因子
    //证明：   如果有两个的话，二者相乘很明显就大于n了呀，就是不对的
    {
        if(n%i==0)
        {
            int s=0;
            while(n%i==0)
            {
                n/=i;
                s++;
            }
        cout<<i<<" "<<s<<endl;
        }
    }
    if(n>1)  cout<<n<<" "<<1<<endl;
    cout<<endl;
}
int main()
{
    int n;
    cin>>n;
    
    while (n -- ){
        int x;
        cin>>x;
        
        divide(x);
    }
    
    return 0;

}

这里我们需要解释一些地方，也就是优化的部分，可想而知

这个时候我们会联想到我们上一篇写的博客：质数的判定--试除法 - 不是小朋友L - 博客园 (cnblogs.com)

然后就可以证明这条性质：

性质：n中最多包含一个大于sqrt(n)的质因子
很明显：如果有两个大于根号n的质因子，那么就相乘就会大于n
所以只要枚举到根号就可以了
关键代码就是：

for(int i=2;i<=n/i;i++)

 if(n>1)  cout<<n<<" "<<1<<endl;//这段代码也是很重要的，他的作用是：因为我们只枚举到根号n，所以如果有一个大于根号n的质因子，我们就单独把他输出出去，属于特判。。

这篇关于分解质因数--试除法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

分解质因数--试除法

相关编程文章