1059 Prime Factors-PAT甲级

题目描述

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1^k1 * p2^k2 *...*pm^km.

 

输入描述:

Each input file contains one test case which gives a positive integer N in the range of long int.

 

输出描述:

Factor N in the format N = p1^k1 * p2^k2 *...*pm^km, where pi's are prime factors of N in increasing order, and the exponent ki is the number of pi -- hence when there is only one pi, ki is 1 and must NOT be printed out.

 

输入例子:

97532468

 

输出例子:

97532468=2^2*11*17*101*1291

打表筛选素数（打表的范围不必很大，否则会造成内存的溢出）

过大的数本身应该就会有比较小的素数为其因子，如果没有，判定其为素数；

第二个是可能留下的商也很大，处理方法同上

满分代码如下：

#include<bits/stdc++.h> using namespace std; const int max_num=1e5; vector<int>ve(max_num,1); vector<int>pri; //埃氏筛选法，素数打表 void is_prime(){ for(int i=2;i<max_num;i++){ if(ve[i]){ pri.push_back(i); for(int j=i+i;j<max_num;j+=i){ ve[j]=0; } } } } map<int,int>mp; int n; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; if(n==1){ cout<<"1=1"<<endl; return 0; } is_prime(); cout<<n<<"="; for(int i=0;i<pri.size();i++){ while(n%pri[i]==0){ mp[pri[i]]++; n/=pri[i]; } if(n==1) break; } map<int,int>::iterator it=mp.begin(); int flag=0; for(;it!=mp.end();it++){ if(flag) cout<<"*"; flag=1; cout<<it->first; if(it->second==1) continue; else cout<<"^"<<it->second; } if(flag==0){// 不在打表内的素数 （本身是素数） cout<<n<<endl; return 0; } if(n>1){//不在打表内的素数 （除下的是素数） cout<<"*"<<n<<endl; } return 0; }