PAT-1059. Prime Factors (25)

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1^k1 * p2^k2 *…*pm^km.

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 *…*pm^km, where pi's are prime factors of N in increasing order, and the exponent ki is the number of pi -- hence when there is only one pi, ki is 1 and must NOT be printed out.

Sample Input:

97532468

Sample Output:

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

分析：（1）先建立素数组（2）要考虑输入为 1 的特例。

参考代码：

#include  
#include  
using namespace std;  
  
#define max 1000  
int prime[max];  
int i;  
int j;  
  
bool isPrime(int temp)  
{  
    int t;  
    bool flag = true;  
    for(t = 2; t <= sqrt(temp); t++)  
        if( temp%t == 0) {flag = false; break;}  
    return flag;  
}  
  
int main()  
{  
    prime[0] = 2;  
    j = 3;  
    for(i=1; i





>input;  
    cout<= 1)  
            {  
                cout< 1)  
                    cout<<"^"<