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

題目大意

給出一個(gè)int范圍的整數(shù)，進(jìn)行質(zhì)因數(shù)分解，質(zhì)因數(shù)按從小到大順序排列。

思路

利用“篩法”求質(zhì)因數(shù)的原理，按照質(zhì)數(shù)從小到大的順序(上限為sqrt(n))，依次去除n，直到無法除盡，則每次剩下的n只可能是其他質(zhì)數(shù)的倍數(shù)；如果n無法被sqrt(n)以內(nèi)的質(zhì)因子除盡，則一定有且僅有一個(gè)大于sqrt(n)的質(zhì)因子。

代碼實(shí)現(xiàn)

#include <cstdio>
#include <cmath>

int facNum = 0;

struct factor
{
    int x, cnt;     // x存儲(chǔ)質(zhì)因子，cnt存儲(chǔ)質(zhì)因子個(gè)數(shù)
} fac[10];      // 對(duì)于int范圍整數(shù)，最多有10個(gè)不同的質(zhì)因子

void Create_Fac(int n)
{
    int num;        // num記錄當(dāng)前質(zhì)因子個(gè)數(shù)
    for (int i = 2; i <= sqrt(n); i++)
    {
        num = 0;
        while (n % i == 0)
        {
            n /= i;
            num++;
        }
        if (num)        // 質(zhì)因子個(gè)數(shù)大于0則記錄到數(shù)組中
        {
            fac[facNum].x = i;
            fac[facNum].cnt = num;
            facNum++;
        }
    }
    if (n > 1)      // 如果無法被sqrt(n)以內(nèi)的質(zhì)因子除盡，則一定有一個(gè)大于sqrt(n)的質(zhì)因子
    {
        fac[facNum].x = n;
        fac[facNum].cnt = 1;
        facNum++;
    }
}

void Print_Fac(int n)
{
    if (n == 0 || n == 1)       // 對(duì)于特殊情況的處理
    {
        printf("%d=%d", n, n);
        return;
    }
    printf("%d=", n);
    for (int i = 0; i < facNum; i++)
    {
        if (i > 0)
            printf("*");
        printf("%d", fac[i].x);
        if (fac[i].cnt > 1)
            printf("^%d", fac[i].cnt);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    Create_Fac(n);
    Print_Fac(n);
    return 0;
}