题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805415005503488

  1. 这题是分解质因子的基本应用，需要注意一下
  2. 测试点3一直没过是因为没有特判n = 1的情况

代码

  1. #include<algorithm>
  2. #include<vector>
  3. #include<iostream>
  4. #include<cstdio>
  5. #include<cmath>
  6. using namespace std;
  8. struct Factor{
  9.     int x, cnt;
  10. }fac[10];
  11. const int maxn = 100010;
  12. vector<int> prime;
  13. vector<bool> is_prime(maxn,true);
  15. void get_prime(int n){
  16.     is_prime[1] = false;
  17.     for(int i = 2; i < maxn; i++){
  18.         if(is_prime[i] == true){
  19.             prime.push_back(i);
  20.             for(int j = 2 * i; j < maxn; j += i){
  21.                 is_prime[j] = false;
  22.             }
  23.         }
  24.     }
  25. }
  27. int main(){
  28.     int n, num = 0;
  29.     scanf("%d",&n);
  30.     if(n == 1) {
  31.         printf("1=1");
  32.         return 0;
  33.     }
  34.     printf("%d=",n);
  35.     get_prime(n);
  36.     int sqr = (int)sqrt(1.0 * n);
  37.     int len = prime.size();
  38.     for(int i = 0; i < len && prime[i] <= sqr; i++){
  39.         if(n % prime[i] == 0){
  40.             fac[num].x = prime[i];
  41.             fac[num].cnt = 0;
  42.             while(n % prime[i] == 0){
  43.                 fac[num].cnt++;
  44.                 n /= prime[i];
  45.             }
  46.             num++;
  47.         }
  48.     }
  49.     if(n != 1){
  50.         fac[num].x = n;
  51.         fac[num++].cnt = 1;
  52.     }
  53.     for(int i = 0; i < num; i++){
  54.         printf("%d",fac[i].x);
  55.         if(fac[i].cnt!=1) printf("^%d",fac[i].cnt);
  56.         if(i != num - 1) printf("*");
  57.     }
  58.     return 0;
  59. }