1059 Prime Factors （25 分)

2019-03-29

1059 Prime Factors （25 分)

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1k1×p2k2×⋯×pmk**m.

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 = p1^k1*p2^k2*…*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:

1	97532468=2^211171011291

作者: HE, Qinming

单位: 浙江大学

时间限制: 200 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

将一个数分解成其质因数的乘积

分析

用map<int,int>存放质数及出现的次数。首先计算根号n内的质数，初始化为0。然后当n不等于1且n不为质数时循环，找根号n内的质因数。找到后出现次数++，并让n除等于此数。最后遍历map输出即可。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include<sstream>

using namespace std;

bool isprime(long int i){
    for(long int t=2;t<=sqrt(i);t++)
        if(i%t==0)
            return false;
        return true;
}
int main() {
    long int n;

    cin>>n;
    cout<<n<<"=";
    if(n==1){
        cout<<1<<endl;
        return 0;
    }

    map<int,int> primes;
    for(long int i=2;i<=sqrt(n);i++){
        if(isprime(i))
            primes[i]=0;
    }
    while(n!=1&&!isprime(n)){
    for(auto it=primes.begin();it!=primes.end();it++){
        if(n%(it->first)==0) {
            n/=(it->first);
            it->second++;
            break;
        }
    }}
    if(isprime(n))
        primes[n]++;
    int f=1;
    for(auto it=primes.begin();it!=primes.end();it++){
        if(it->second!=0) {
            if(f==0){
                cout<<"*";
            }
            f=0;
            cout << it->first;
            if(it->second!=1)
                cout<<"^"<<it->second;
        }
    }
    return 0;
}