解题思路

首先把int范围内的素数计算出来存入数组中。然后从素数表中去除一个数与给定的n试除，如果能除尽说明是该数的因子，然后一直除并记录所除的次数，最后按照格式将素数因子与幂次一次打印出来，over！
空说无凭，show me the code!

版本1

#include<cstdio>
#include<cmath>
const int maxn=100005;
int prime[maxn],num=0;
bool p[maxn]={0};
void find_prime(){               //筛选素数 
	for(int i=2;i<maxn;i++){
		if(p[i]==false){
			prime[num++]=i;

			for(int j=i+i;j<maxn;j+=i){
				p[j]=true;
			}
		}
	}
}
struct E{  //用来存素数因子和出现的次数 
	int x;
	int cnt;
}buf[11];
int main(){
	int n;
	find_prime();
	scanf("%d",&n);
	int k=0;
	if(n==1)
	   printf("1=1"); //特殊处理，注意，1不是素数，所以也不可能是因子 
	else{
		printf("%d=",n);
		int sqr=(int)sqrt(1.0*n);
		for(int i=0;i<num&&i<=sqr;i++){
			if(n%prime[i]==0){
				buf[k].x=prime[i];

				buf[k].cnt=0;
				while(n%prime[i]==0){
					buf[k].cnt++;
					
					n=n/prime[i];
				}
				k++;
			}
			if(n==1) break; 
		}
		if(n!=1)  //如果存在一个大于sqrt(n)的因子，那一定是他本身，即这个数是个素数，唯一的因子就是自己 
		{
			buf[k].x=n;
			buf[k++].cnt=1;
		}
		for(int i=0;i<k;i++){
			if(i>0) 
			printf("*");
			printf("%d",buf[i].x);
			if(buf[i].cnt>1)
			  printf("^%d",buf[i].cnt);
		}
	}
	
	return 0;
}

版本2

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5; //这个范围内的素数 
int p[maxn]={0};
int prime[maxn];
struct node{
	int num,factor;
}E[10];
int k=0;

void findPrime(){
	for(int i=2;i<maxn;i++){
		if(p[i]==0){
			prime[k++] = i;
			for(int j=i+i;j<maxn;j+=i){
				p[j]=1;
			}
		}
	}
}
int main(){
	int x;
	scanf("%d",&x);
	if(x==1){
		printf("1=1");
		return 0;
	}
	findPrime();
	int n = x;
	int j=0;
	int sqr = sqrt(n); 
	for(int i=0;i<k && prime[i] <= sqr; i++){
		if(n%prime[i]==0) j++;
		while(n%prime[i]==0){
			E[j].num = prime[i];
			E[j].factor++;
			n /= prime[i];
		}
		if(n==1) break;
	}
	if(n!=1){ //这个步骤很经典！！！
		j++;
		E[j].num = n;
		E[j].factor=1;
	}
	printf("%d=",x);
	
	for(int i=1;i<=j;i++){
		if(i!=1) printf("*");
		printf("%d",E[i].num);
		if(E[i].factor != 1) printf("^%d",E[i].factor);
	}
	return 0;
}