SP4942题解

金霸王电池 · 2022-03-03 16:50:19 · 题解

分解质因数板子题。

枚举 i 从 2 到 \sqrt n ，每次判断是不是 n 的因数，不是就跳过，是则 while 循环判断 n 是否为 i 的倍数，是则

cnt++,n/=i;

最后输出。

最后，如果 n 还不是一，说明没除尽，补上就是了。

那么，i 为什么一定是质数呢？如果 i 不是质数，那么它肯定有一个质因子在前面出现过，那么现在的 n 绝对不是这个因子的倍数，也就不是 i 的倍数了。

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n; 
signed main(){
    while(1){
        cin>>n;
        if(!n)return 0;//判断结束
        for(int i=2;i<=sqrt(n);i++)//枚举i
            if(n%i==0){
                int ans=0;//计数
                while(n%i==0){
                    ans++;
                    n/=i;
                }
                cout<<i<<"^"<<ans<<" ";
            }
        if(n!=1)cout<<n<<"^"<<1;//判断有没有除尽
        cout<<endl;
    }
}