分解质因数2.0
2025-11-07 22:09:31
发布于:广东
代码核心:利用线性筛每个数都被自己的最小质因子所筛掉的特性
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll x;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>x;
vector<ll> z;
vector<bool> f(x+1,true);
vector<ll> w(x+1);
for(ll i=2;i<=x;i++){
if(f[i]){
z.push_back(i);
w[i]=i;
}
for(auto t:z){
if(i*t>x) break;
f[i*t]=false;
w[i*t]=t;
if(i%t==0) break;
}
}
while(x!=1){;
cout<<w[x]<<' ';
x/=w[x];
}
return 0;
}
这里空空如也













有帮助,赞一个