PAT甲级1059 Prime Factors

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

• 题解：先建立一个一万以内的素数表，然后再从第一个素数开始往后判断是否为n的因子，并统计这个素因子出现的次数。注意特判 n == 1的情况。

  #include <iostream>
  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  #include <map>
  #include <vector>
  #define ll long long
  using namespace std;
  map<ll, int> mp;
  vector<ll> v;
  void Prime(ll n){
      mp.clear();
      for(ll i = 2; i <= 10000; i++){
          if(mp[i] == 1) continue;
          v.push_back(i);//i是素数
          for(ll j = i; j <= 10000/i; j++){
              mp[i*j] = 1;
          }
      }
  }
  int main()
  {
      ll n, cnt = 0;
      scanf("%lld", &n);
      if(n == 1){//特例
          printf("1=1\n");
          return 0;
      }
      Prime(n);
      printf("%lld=", n);
      int flag = 0;//flag用于标记是否是第一个素因子，用于输出格式的控制
      for(int i = 0; i < v.size(); i++){
          cnt = 0;
          if(n % v[i] == 0){
              if(flag) printf("*%lld", v[i]);
              else printf("%lld", v[i]);
              flag = 1;
              while(n % v[i] == 0){
                  n /= v[i];
                  cnt++;
              }
              if(cnt > 1){//该素因子个数大于1则输出指数
                  printf("^%lld", cnt);
              }
          }
      }
      printf("\n");
      return 0;
  }