题目

http://noi.openjudge.cn/ch0113/22/

思路

素数筛，p开始筛选掉所有的2p，3p，4p，而后使用唯一分解定理

源码

//
//  22.cpp
//  test
//
//  Created by bytedance on 2020/9/7.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;


int ps[1000];
int main(){
    int n;
    cin >> n;
    memset(ps,0,sizeof(ps));
    for(int i = 2;i < 1000;++i){
        for(int j = i*2;j<1000;j+=i){
            ps[j] = 1;
        }
    }
    string res = "";
    for(int i = 2;i<1000;++i){
        if(ps[i]==1||n==1)continue;
        int cnt = 0;
        while(n%i==0){
            n/=i;
            cnt++;
        }
        if(cnt!=0){
            if(cnt==1)res=res+"*"+to_string(i);
            else res=res+"*"+to_string(i)+"^"+to_string(cnt);
        }
    }
    res.erase(res.begin());
    cout <<res;
    return 0;
}