题解 | #分解质因数#

这道题只要知道一个结论后就可以做了，对于一个数，其质因数最多有一个大于的，这个通过反证法也很容易证明。

知道这个后，，所以我们只需要预处理出以内的所有质数即可，时间复杂度为。

#include <iostream>
#include<vector>
using namespace std;
using ll=long long;
vector<int> primes;
bool vis[1000010];
void init(){
    vis[0]=vis[1]=1;
    for(int i=2;i<=1000000;i++){
        if(!vis[i]) primes.push_back(i);

        for(int p:primes){
            if(i*p>1000000) break;
            vis[i*p]=1;
            if(i%p==0) break;
        }
    }
}
int main() {
    init();
    ll n;
    cin >> n;
    for(int p:primes){
        if(n%p==0){
            while(n%p==0){
                cout << p << " ";
                n/=p;
            }
        }
    }
    if(n>1) cout << n << endl;
}
// 64 位输出请用 printf("%lld")