题解 | 质数因子

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> vi;

//const int N=;

int main()
{
    IOS
    int n;
    cin>>n;
    for(int i=2; i<=sqrt(n); i++)
    {
        while(n%i==0) n/=i, cout<<i<<" ";
    }
    if(n>1) cout<<n;
    return 0;
}

根号n的时间复杂度，由分解唯一性定理可以知道最后剩下的如果大于1，那一定也是一个质数

按代码这样从小到大找即可

#牛客春招刷题训练营#