前言

传送门

正文


参考题解

#include<iostream>
#include<cmath>
using namespace std;
/* 题意： 给定一个数n，将其分解成为质因子的乘法形式（从小到大） 思路：直接套用质因子分解模板即可。注意首先打印出素数表，然后再 进行质因子分解 注意点： 1、素数的判断时循环条件是小于等于根号n 2、打印素数表时，从1开始循环，并且循环条件是小于maxn 3、注意特判1 4、注意枚举质因子时如何求每个质因子的个数,以及n是变化的，故注意不能再循环条件中求sqrt(n) */
const int maxn=1e5+10;//素数表长，因为题目n不超过int，故sqrt(n)不超过1e5
int prime[maxn],pNum=0;//prime数组存放所有的素数,pNum表示素数的个数
bool  p[maxn]={false};//p[i]==true表示i是素数
//判断n是否是素数
bool isPrime(int n){ 
	if(n<=1)return false;
	for(int i=2,j=(int)sqrt(n*1.0);i<=j;i++){
		if(n%i==0)return false;
	} 
	return true;
}
//打印素数表 ，注意从1开始，小于maxn 
void findPrime(){
	 for(int i=1;i<maxn;i++){
	 	if(isPrime(i)){
	 		prime[pNum++]=i;
	 		p[i]=true;//i是素数 
		}
	 }
} 
struct factor{
	int x,cnt;//x表示质因子，cnt表示其个数 
}fact[10];//长度为10即可，因为2*35*7*...*29已经超过了int型范围
 
int main(){
	findPrime();//打印素数表 
	int n,num=0;//num表示不同质因子的个数 
	cin>>n; 
	if(n==1){//特判1
		cout<<"1=1\n";
	}else{
		cout<<n<<"="; 
		//枚举根号n以内的质因数 
		for(int i=0,j=(int)sqrt(n*1.0);i<pNum&&prime[i]<=j;i++){//分解质因子 
			if(n%prime[i]==0){
				fact[num].x=prime[i];
				fact[num].cnt=0;
				while(n%prime[i]==0){//求质因数prime[i]的个数 
					fact[num].cnt++;
					n/=prime[i];
				}
				num++;
			} 
			if(n==1)break; 
		}
		
		if(n!=1){//说明n无法被根号n以内的质因子除尽，故必有大于根号n的质因子 
			fact[num].x=n;
			fact[num].cnt=1;
			num++; 
		} 
		//输出
		for(int i=0;i<num;i++){
			if(i!=0)cout<<"*";
			cout<<fact[i].x;
			if(fact[i].cnt>1){
				cout<<"^"<<fact[i].cnt;
			}
		}
	} 
	return 0;
}