G5001 [GESP202309 五级] 因数分解 题解

知识点：质因数分解、试除法、格式化输出。

解题思路

从2开始试除当前n，遇到因数就连续除尽并记录指数。试除结束后剩余大于1的部分也是一个质因数。

为什么正确

每次除尽最小可用因数，记录的是唯一分解中的完整指数；未找到小因数的剩余部分只能是质数。

易错点

指数为1时不打印^1；各项之间用空格星号空格，不能多输出乘号。

复杂度

时间O(√原n)，空间O(log n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin>>n;
    vector<pair<long long,int>>f;
    for(long long p=2;p*p<=n;p++) {
        if(n%p)continue;
        int c=0;
        while(n%p==0) {
            n/=p;
            c++;
        }
        f.push_back({p,c});
    }
    if(n>1)f.push_back({n,1});
    for(int i=0;i<(int)f.size();i++) {
        if(i)cout<<" * ";
        cout<<f[i].first;
        if(f[i].second>1)cout<<"^"<<f[i].second;
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。