PAT甲级1059 Prime Factors 质因数分解+线性筛素数

Solution：

• 题目要求：要求对一个long int型正整数进行质因数分解。我们知道，一个合数可以写成若干个质数相乘的结果。
• 用线性筛素数的方法。

代码如下：

//质因数分解+线性筛素数#include<iostream>#defineMAX 1000010using namespace std;longn;//判断的数nbool isprime[MAX];intans[MAX];//存储质数的个数voideratos(){//线性筛素数for(inti=0;i<=MAX;i++){isprime[i]=true;}isprime[0]=isprime[1]=false;//删除0和1for(inti=2;i*i<=MAX;i++){//留下i，删除i的倍数if(isprime[i]){intj=i+i;while(j<=MAX){isprime[j]=false;j=j+i;}}}}intmain(){cin>>n;if(n==1){cout<<"1=1";return0;}eratos();longt=n;while(t>1){for(inti=2;i<=MAX;i++){if(isprime[i]==true&&t%i==0){ans[i]++;t/=i;}}}cout<<n<<"=";intflag=false;for(inti=2;i<MAX;i++){if(ans[i]==1){if(flag==false){cout<<i;flag=true;}else{cout<<"*"<<i;}}elseif(ans[i]>1){if(flag==false){cout<<i<<"^"<<ans[i];flag=true;}else{cout<<"*"<<i<<"^"<<ans[i];}}}return0;}