## 题目

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1kp2k2×⋯×pmk**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 `=` p1`^`k1`*`p2`^`k2`*``*`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:

 ``````1 `````` ``````97532468 ``````

### Sample Output:

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

## 分析

• 对于因子查找的结论： 如果n存在[1,n]的因子，则在sqrt(n)的两边对称存在
• 对于质因数有一个结论：对一个正整数n来说，如果它存在[2,n]范围内的质因子，要么这些质因子全部小于等于sqrt(n)，要么只存在一个位于[sqrt(n),n]的质因子。

## 代码

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 `````` ``````#include #include int primeList[100001]; int primeNum=0; struct factor { int f; int e; }factor[100]; bool isPrime(int n) { int sqrtn = sqrt(n); for(int i=2;i<=sqrtn;i++) if(n%i==0) return 0; return 1; } void buildPrime() { for(int i=2;i<100001;i++) if(isPrime(i)) primeList[primeNum++]=i; } int main() { long int n; scanf("%ld",&n); printf("%ld=",n); if(n==1) printf("1"); else { buildPrime(); int num=0; int sqrtn=sqrt(n); //find factor rang of [2...sqrtn] for(int i=0;primeList[i]<=sqrtn;i++) { if(n%primeList[i]==0) { factor[num].f=primeList[i]; while(n%primeList[i]==0) { n/=primeList[i]; factor[num].e++; } num++; } } if(n>1) { factor[num].f=n; factor[num].e=1; num++; } //print for(int i=0;i0)printf("*"); if(factor[i].e>1) printf("%d^%d",factor[i].f,factor[i].e); else printf("%d",factor[i].f); } } return 0; } ``````