PAT(Advanced)1059 Prime Factors (25 分)

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

题目解读：把一串数字进行因式分解，对重复的素数要用指数的表达方式。

解题思路：很简单的暴力算法，因为只有一个数字也不需要剪枝就可以得出结果。map很适合做这种有固定顺序的，需要记数的题。

这次做题有一些误区，比如map中对value的加法应该用prime[i]++而不是prime.at(i)++。

还有对循环的判断应该是小于NUM而不是它的平方根，还好这道题通过很小的数就可以看出哪里错了，没有long int的溢出问题。

AC代码：

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
bool isPrime( long int n ){
  if (n == 1) return false;
  for (long int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0)return false;
  }
  return true;
}
int main()
{
  long int num;
  map<long int,int> primetime;
  cin >> num;
  cout << num << "=";
  int flag = 1;
  while (num != 1 && flag == 1) {
    flag = 0;
    for (long int i = 2; i <= num; i++) {
      if (isPrime(i) && num % i == 0) {
        primetime[i]++;
        num = num/i;
        flag = 1;
        break;
      }
    }
  }
  if (primetime.size() == 0) {
    cout <<"1*"<< num << endl;
  }
  int count = 1;
  for (auto value : primetime) {
    if (value.second != 1)
      cout << value.first << "^" << value.second;
    else cout << value.first;
    if (count < primetime.size())
      cout << "*";
    count++;
  }
}