1059 Prime Factors

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p​1​​​k​1​​​​×p​2​​​k​2​​​​×⋯×p​m​​​k​m​​​​.

Input Specification:

Each input file contains one test case which gives a positive integer N in the range of long int.

Output Specification:

Factor N in the format N = p​1​​^k​1​​*p​2​​^k​2​​*…*p​m​​^k​m​​, where p​i​​'s are prime factors of N in increasing order, and the exponent k​i​​ is the number of p​i​​ -- hence when there is only one p​i​​, k​i​​ is 1 and must NOT be printed out.

Sample Input:

97532468

Sample Output:

97532468=2^2*11*17*101*1291

实现代码：

#include<cstdio>
#include<cmath>
const int maxn = 100010;
bool is_prime(int n)
{
	if(n == 1) return false;
	int sqr = (int) sqrt(1.0*n);
	for(int i=2;i<=sqr;i++){
		if(n%i==0) return false;
	}
	return true;
 } 
 int prime[maxn],pNum=0;
 void Find_Prime(){
 	for(int i=1;i<maxn;i++ ){
 		if(is_prime(i)==true){
 			prime[pNum++] = i;
		 }
	 }
 }
 struct factor{
 	int x,cnt;
 	
 }fac[10];
 int main()
 {
 	Find_Prime();
 	int n,num=0;
 	scanf("%d",&n);
 	if(n == 1) printf("1=1");
 	else{
 		printf("%d=",n);
 		int sqr = (int) sqrt(1.0*n);
 		for(int i=0;i<pNum&&prime[i]<=sqr;i++){
 			if(n%prime[i]==0){
 				fac[num].x=prime[i];
 				fac[num].cnt=0;
 				while(n%prime[i]==0){
 					fac[num].cnt++;
 					n/=prime[i];
				 }
				 num++;
			 }
			 if(n == 1) break;
			 
		 }
		 if(n != 1){
		 	fac[num].x=n;
		 	fac[num++].cnt=1;
		 }
		 for(int i=0;i<num;i++){
		 	if(i>0) printf("*");
		 	printf("%d",fac[i].x);
		 	if(fac[i].cnt>1){
		 		printf("^%d",fac[i].cnt);
			 }	 
		}
	 }
	 return 0;
 }

 

结果如下：