PAT 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₁^k₁ * p₂^k₂ *…*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₁^k₁ * p₂^k₂ *…*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 <cstdio> #include <map> using namespace std; int isPrime(int n) { for(int i = 2; i * i <= n; i++) { if(n % i == 0) return false; } return true; } int main() { int num; cin>>num; map<int,int> MAP; int m = num; if(num == 1) { cout<<num<<"="<<1<<endl; return 0; } for(int i = 2; i <= m && num != 1; i++) { if(isPrime(i)) { while(num % i == 0) { MAP[i]++; num /= i; } } } int size = MAP.size(); int count = 0; map<int,int>::iterator it = MAP.begin(); cout<<m<<"="; for(;it != MAP.end(); ++it) { count++; cout<<it->first; if(it->second > 1) cout<<"^"<<it->second; if(count < size) cout<<"*"; } return 0; }