题解 | 分解质因数

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MAXN 1000010
int primes[MAXN],cnt;
bool st[MAXN];
void gprimes(int n){
	for(int i=2;i<=n;i++){
		if(!st[i])primes[cnt++]=i;
		for(int j=0;primes[j]*i<=n;j++){
			st[primes[j]*i]=1;
			if(i%primes[j]==0)break;
		}
	}
}
signed main(){
	ios;
	int n;
	cin>>n;
	gprimes(1000000);
	for(int i=0;i<cnt;i++){
		while(n%primes[i]==0){
			cout<<primes[i]<<" ";
			n/=primes[i];
		}
		if(n==1)break;
	}
	if(n!=1)cout<<n<<endl;
	return 0;
}