PAT-Prime Factors (25)

题目来源Prime Factors (25)题面点击链接自行查看注意点因子从小到大输出思路简介素数筛然后选因子即可遇到的问题特判 1因为1既不是质数也不是合数质数题经典大坑了代码/** * https://www.nowcoder.com/pat/5/problem/4112 * 素数筛 */#includebits/stdc.husingnamespacestd;typedeflonglongll;constll N0x7ffff;intk0;vectorllprime(N),vis(N);voidEuler_sieve(){for(inti2;iN;i){if(!vis[i])prime[k]i;for(intj0;jkprime[j]*iN;j){vis[prime[j]*i]1;if(i%prime[j])break;}}}boolcmp(pairll,inta,pairll,intb){returna.firstb.first;}voidsolve(){Euler_sieve();ll n;cinn;coutn;if(n1){cout1;return;}vectorpairll,intres;for(inti0;ikprime[i]*prime[i]n;i){if(n%prime[i])continue;intt0;while(!(n%prime[i])){n/prime[i];t;}pairll,inta{prime[i],t};res.emplace_back(a);}if(n!1){pairll,inta{n,1};res.emplace_back(a);}sort(res.begin(),res.end(),cmp);intlenres.size();for(inti0;ilen;i){coutres[i].first;if(res[i].second1){cout^res[i].second;}if(i!len-1)cout*;}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//fstream in(in.txt,ios::in);cin.rdbuf(in.rdbuf());intT1;//cinT;while(T--){solve();}return0;}