PAT-A 真题- 1059. Prime Factors

原题干：

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

题目大意：

给定一个int范围的数字，对它进行质因子分解。

这道题有几处易错点：

1、第三个测试点输入的数据为1，如果程序对1做出正确判断，将会出错

2、如果有多个相同的质数，记得要写成乘方的形式。例如8=2^3

我的思路是定义一个判断是否是素数的函数，然后从2开始除输入的数字进行判断，如果发现无法整除，就移动到下一个素数进行判断。直到输入的数字被除到1为止。

代码如下：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

bool isPrime(long int n){
  if(n == 2) return true;
  for(long int i = 2; i < n / 2 + 1; i++)
    if(n % i == 0) return false;
  return true;
}

long int NextPrime(){
  static long int prime = 1;
  do{
    prime++;
  }while(!isPrime(prime));
  return prime;
}

int main(){
  long int num;
  cin >> num;
  cout << num << '=';
  bool isFrist = true;
  if(num == 1) cout << 1;
  else
    while(num != 1){
      int cnt = 0;
      long int prime = NextPrime();
      for(; num % prime == 0; cnt++) num /= prime;
      if(cnt == 0) continue;
      if(isFrist == false) cout << '*';
      else isFrist = false;
      cout << prime;
      if(cnt > 1) cout << '^' << cnt;
    }
  return 0;
}