A1059

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 = p 1 k 1 ×p 2 k 2 ×⋯×p m k 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 = p 1 ^k 1 *p 2 ^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

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<cmath>
#include<set>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
int isprime(long x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0)return 0;
    }
    return 1;
}
int main(){
    long N,M;
    cin>>N;
    long n=N;
    vector<long>ans,mp(100000,0);
    if(N==1){
        cout<<N<<'='<<N;
        return 0; 
    }
    while(n){
        int i,is=0;
        for(i=2;i<=sqrt(N);i++){
            if(isprime(i)&&n%i==0){
                if(mp[i]==0) ans.push_back(i);
                mp[i]++;
                is=1;
                break;
            }
        }
        if(is) n/=i;
        else if(n!=1){
            ans.push_back(n);
            mp[n]++;
            break;
        }
        else break;
    }
    cout<<N<<'=';
    for(int i=0;i<ans.size();i++){
        if(i)printf("*");
        cout<<ans[i];
        if(mp[ans[i]]>1)cout<<'^'<<mp[ans[i]];
    }
    return 0;
}

A1059

1059 Prime Factors (25分)

NTaurus