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

Solution题目要求要求对一个long int型正整数进行质因数分解。我们知道一个合数可以写成若干个质数相乘的结果。用线性筛素数的方法。代码如下//质因数分解线性筛素数#includeiostream#defineMAX 1000010using namespace std;longn;//判断的数nbool isprime[MAX];intans[MAX];//存储质数的个数voideratos(){//线性筛素数for(inti0;iMAX;i){isprime[i]true;}isprime[0]isprime[1]false;//删除0和1for(inti2;i*iMAX;i){//留下i删除i的倍数if(isprime[i]){intjii;while(jMAX){isprime[j]false;jji;}}}}intmain(){cinn;if(n1){cout11;return0;}eratos();longtn;while(t1){for(inti2;iMAX;i){if(isprime[i]truet%i0){ans[i];t/i;}}}coutn;intflagfalse;for(inti2;iMAX;i){if(ans[i]1){if(flagfalse){couti;flagtrue;}else{cout*i;}}elseif(ans[i]1){if(flagfalse){couti^ans[i];flagtrue;}else{cout*i^ans[i];}}}return0;}