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 = 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

tip:题目的要求比较清楚，就是寻找所给数的质数因数，从小到大一个一个取因数即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
map<ll,int> exponent; //用于存放相应的指数
bool isPrime(ll x){
    if (x==1)
        return false;
    if (x==2){
        return true;
    }
    for (ll i=2;i*i<=x;++i){
        if (x%i==0)
            return false;
    }
    return true;
}
ll find_factor(ll x){ //寻找x最小的质数因数
    for (ll i=2;i*i<=x;++i){
        if (x%i==0&&isPrime(i))
            return i;
    }
    return -1;
}
int main(){
    cin>>n;
    ll rest=n;
    while(!isPrime(rest)){
        ll factor=find_factor(rest);
        if (factor==-1)
            break;
        exponent[factor]++;
        rest=rest/factor;
    }
    exponent[rest]++;
    cout<<n<<"=";
    map<ll,int>::iterator it;
    for (it=exponent.begin();it!=exponent.end();++it){
        cout<<it->first;
        if (it->second>1)
            cout<<"^"<<it->second;
        if (it!=(--exponent.end()))
            cout<<"*";
    }
}