PAT A 1059 Prime Factors (25分)

97532468

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

#include <iostream>
using namespace std;
const int MAXN = 100000;
int prime[MAXN], k, flag, flag2;
long int n;
void init() {
    prime[0] = prime[1] = 0;
    for (int i = 2; i*i <= MAXN; i++) {
        if (prime[i]) {
            for (int j = i*i; j <= MAXN; j+=i)
                prime[j] = 0;
        }
        
    }
}
int main() {
    fill(prime, prime + MAXN, 1);
    init();
    cin >> n;
    printf("%ld=", n);
    if (n == 1)    printf("1");
    for (int i = 2; n >= 2; i++) {
        flag = k = 0;
        while (prime[i]==1 && n%i == 0) {
            k++; n /= i;
            flag = 1;
        }
        if (flag) {
            if (flag2) printf("*");
            printf("%d", i);
            flag2 = 1;
        }
        if (k >= 2) {
            printf("^%d", k);
        }
    }
    return 0;
}