分解质因数--试除法-Toy模板网

这篇具有很好参考价值的文章主要介绍了分解质因数--试除法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

分解质因数--试除法

 #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的质因子，我们就单独把他输出出去，属于特判。。

文章来源地址https://www.toymoban.com/news/detail-462128.html

到了这里，关于分解质因数--试除法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

分解质因数--试除法

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2