pat1059 Prime Factors

题意：分解质因数

思路：筛法打表，暴力分解

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAX_N = 1000000;

int isNotPrim[MAX_N];
int prime[MAX_N], len;

void init() {
    memset(isNotPrim, 0, sizeof(isNotPrim));
    len = 0;
    for (int i = 2; i < MAX_N; i++) {
        if (!isNotPrim[i]) {
            prime[len++] = i;
            for (int j = i + i; j < MAX_N; j += i) {
                isNotPrim[j] = 1;
            }
        }
    }
}

int a;
int cnt[MAX_N];
int p[MAX_N], lenp;

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    init();
    memset(cnt, 0, sizeof(cnt));
    lenp = 0;
    scanf("%d", &a); int t = a;
    for (int i = 0; i < len; i++) {
        if (t % prime[i] == 0) {
            p[lenp++] = prime[i];
            while (t % prime[i] == 0) {
                cnt[prime[i]]++;
                t /= prime[i];
            }
        }
        if (t == 1) break;
    }
    bool flag = false;
    printf("%d=", a);
    if (a == 1) printf("1");
    else {
        for (int i = 0; i < lenp; i++) {
            if (flag) printf("*");
            else flag = true;
            printf("%d", p[i]);
            if (cnt[p[i]] > 1) printf("^%d", cnt[p[i]]);
        }
    }
    printf("\n");
    return 0;
}