Given any positive integer $N$, you are supposed to find all of its prime factors, and write them in the format $N=p1^{k_1}\times p2^{k_2}\times …\times pm^{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$ = 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.

Note: in case $N$ has no prime factor, simply print the only factor it has. (Thanks to 王忠文 for pointing out this special case.)

Sample Input:

97532468

Sample Output:

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

#include <iostream>
#include <string>
#include <algorithm>
#include<math.h>
#include<queue>
#include<vector>
using namespace std;

int N;
//打印素数表
int prime[100010];
int p_num = 0;
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;
}

void prime_table() {
    for (int i = 2; i < 100010; i++) {
        if (is_prime(i) == true) {
            prime[p_num] = i;
            p_num++;
        }
    }
}

struct factor {
    int x;
    int cnt;
}fac[10];

int main() {
    cin >> N;
    cout << N << '=';
    prime_table();
    int prime_count = 0;
    if (N == 1)cout << '1';
    else {
        for (int i = 0; i < p_num; i++) {
            if (N % prime[i] == 0) {
                fac[prime_count].x = prime[i];
                fac[prime_count].cnt = 0;
                while (N % prime[i] == 0) {
                    fac[prime_count].cnt++;
                    N = N / prime[i];
                }
                prime_count++;
            }
        }
        if (N != 1) {
            fac[++prime_count].x = N;
            fac[prime_count].cnt = 1;
        }
        for (int i = 0; i < prime_count - 1; i++) {
            if (fac[i].cnt > 1)cout << fac[i].x << '^' << fac[i].cnt << '*';
            else cout << fac[i].x << '*';
        }
        if (fac[prime_count - 1].cnt > 1)cout << fac[prime_count - 1].x << '^' << fac[prime_count - 1].cnt;
        else cout << fac[prime_count - 1].x;
    }
}