PAT-Prime Factors (25)

题目来源

Prime Factors (25)
题面点击链接自行查看

注意点

• 因子从小到大输出

思路简介

素数筛然后选因子即可

遇到的问题

1. 特判 1！！！，因为1既不是质数也不是合数！！！质数题经典大坑了

代码

/** * https://www.nowcoder.com/pat/5/problem/4112 * 素数筛 */#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constll N=0x7ffff;intk=0;vector<ll>prime(N),vis(N);voidEuler_sieve(){for(inti=2;i<N;++i){if(!vis[i])prime[k++]=i;for(intj=0;j<k&&prime[j]*i<N;++j){vis[prime[j]*i]=1;if(i%prime[j])break;}}}boolcmp(pair<ll,int>a,pair<ll,int>b){returna.first<b.first;}voidsolve(){Euler_sieve();ll n;cin>>n;cout<<n<<'=';if(n==1){cout<<1;return;}vector<pair<ll,int>>res;for(inti=0;i<k&&prime[i]*prime[i]<n;++i){if(n%prime[i])continue;intt=0;while(!(n%prime[i])){n/=prime[i];t++;}pair<ll,int>a={prime[i],t};res.emplace_back(a);}if(n!=1){pair<ll,int>a={n,1};res.emplace_back(a);}sort(res.begin(),res.end(),cmp);intlen=res.size();for(inti=0;i<len;++i){cout<<res[i].first;if(res[i].second>1){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());intT=1;//cin>>T;while(T--){solve();}return0;}