题目
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;
}