PAT Advanced1059 Prime Factors（建立素数表）

链接：PAT Advanced1059

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p₁^k??? × p₂^k?? × ? × p_?m ^km??? .

Input Specification:

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

Output Specification:

Factor N in the format N = p₁?? ^ k?₁ * p₂?? ^ k_?2?? * … * p_?m?? ^ k_?m?? , where p_?i?? 's are prime factors of N in increasing order, and the exponent k?_i?? is the number of p_i?? – hence when there is only one p_i? , k?_i?? is 1 and must NOT be printed out.

Sample Input:

97532468

Sample Output:

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

要求就是质因子（素数因子）分解：将一个正整数n写成一个或多个质数的乘积的形式。

对于一个正整数n来说，如果它存在1和本身以外的因子，那么一定是在sqrt(n)的左右成对出现。

所以，只需要建立 [2 , sqrt(n)] 范围内的素数表，然后遍历素数表找出n的因子及个数。

建立素数表：
① 逐个判断： 遍历 [2 , sqrt(n)] ，判断每一个是否为素数。时间复杂度为O(n√n)

②埃氏筛选法（Eratosthenes 筛选法）:从第一个素数 “2” 的开始，筛选掉 2~maxn 的所有 “2” 的倍数，继续遍历，若遍历到的数已被筛选掉，则跳过；反之该数为素数，进行同 “2” 的操作。
时间复杂度为O(nloglogn)

ps.可以利用map、set容器在内部自动从小到大排序的特性。

以下代码：

#include<iostream>
#include<set>
#include<cmath>
#include<map>
using namespace std;
set<int> prime;            //用于存储素数表
map<int,int> ans;
void find_prime(int maxn)  //建立素数表
{
    set<int> temp;         //用于存储已被筛选掉的元素for(int i=2;i<=maxn;i++){
    if(!temp.count(i))             //若未被筛选掉{
    prime.insert(i);           //则是素数for(int j=i;j<=maxn;j+=i)  //并筛选掉其所有倍数temp.insert(j);}}
}
int main()
{
      int temp,n;cin>>n;temp=n;find_prime(sqrt(n));set<int>::iterator it1;for(it1=prime.begin();it1!=prime.end();it1++){
    int t=*it1;while(n%t==0){
    if(!ans.count(t))ans[t]=1;elseans[t]++;n/=t;}}cout<<temp<<"=";if(ans.empty())   //不要漏了这个cout<<temp;else{
    map<int,int>::iterator it2;for(it2=ans.begin();it2!=ans.end();it2++){
    if(it2!=ans.begin())cout<<"*";cout<<(*it2).first;if((*it2).second!=1)cout<<"^"<<(*it2).second;}}return 0;
}