PAT A1059 Prime Factors（分解质因数板题）

    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <cstdio>
    #include <cmath>
    using namespace std;
    //数组不需要开到int型最大值那么大
    //分解质因数后质因数不会太大
    const int maxn = 10000;
    bool judge_prime[maxn];
    int prime[maxn];
    int num_fac, num_prime = 0;
    void get_prime()
    {
    // 素数筛法得到素数表
    memset(judge_prime, true, sizeof(judge_prime));
    judge_prime[1] = judge_prime[0] = false;
    for (int i = 2; i < maxn; i++)
    {
        if (judge_prime[i] == true)
            for (int j = i + i; j < maxn; j += i)
                judge_prime[j] = false;
    }
    for (int i = 2; i <= maxn; i++)
    {
        if (judge_prime[i])
            prime[num_prime++] = i;
    }
    }
    struct Factor
    {
    int x, count; //x为质因子，count为其个数初始化为0
    Factor()
    {
    	count=0;
    }
    } fac[100];
    void prime_factor(int n)
    {
    // n==1时单独处理
    if (n == 1)
        fac[num_fac++].x = 1, fac[num_fac].count = 1;
    else
    {
        // 从2到n的开方区间内判断质因数
        int bound = (int)sqrt(1.0 * n);
        for (int i = 0; i < num_prime && prime[i] <= bound; i++)
        {
            if (n % prime[i] == 0)
            {
                fac[num_fac].x = prime[i];
                while (n % prime[i] == 0)
                {
                    // 计算同一个质因数出现几次
                    n = n / prime[i];
                    fac[num_fac].count++;
                }
                num_fac++;
            }
        }
        // 如果无法被sqrt(n)以内的质因数除尽
        // 一定有一个>sqrt(n)的质因数
        if (n != 1)
        {
            fac[num_fac].x = n;
            fac[num_fac].count++;
            num_fac++;
        }
    }
    }
    int main()
    {
    // freopen("in.txt", "r", stdin);
    get_prime();
    int n;
    while (~scanf("%d", &n))
    {
        num_fac = 0;
        prime_factor(n);
        printf("%d=", n);
        for (int i = 0; i < num_fac; i++)
        {
            if (i > 0)
                printf("*");
            printf("%d", fac[i].x);
            if (fac[i].count > 1)
                printf("^%d", fac[i].count);
        }
        printf("\n");
    }
    return 0;
    }