a010: 因數分解

內容 ：
        各位在國小時都學過因數分解，都瞭解怎麼樣用紙筆計算出結果，現在由你來敎電腦做因數分解。
       因數分解就是把一個數字，切分為數個質數的乘積，如 12=2^2 * 3
其中, 次方的符號以 ^ 來表示。

輸入說明 ：
一個整數, 大於1 且 小於等於 1000000

輸出說明 ：
一個字串

範例輸入 ：
20
17
999997

範例輸出 ：
2^2 * 5
17
757 * 1321

程式碼：

#include <stdio.h>
#include <math.h>
int main()
{
    int i,j,n;
    int total_factor,check,sqr;
    int factor[78500];
    
    factor[0] = 2;
    factor[1] = 3;
    total_factor = 2;
    i=5;
    
    while(i<999984)
    {
        check = 1;
        sqr = sqrt(i);
        for(j=2;j<total_factor;j++)
        {
            if(i%factor[j] == 0)
            {
                check = 0;
                break;
            }
            else if(sqr < factor[j])
                break;
        }
        if(check)
        {
            factor[total_factor] = i;
            total_factor++;
        }
        i=i+2;
        
        check = 1;
        sqr = sqrt(i);
        for(j=2;j<total_factor;j++)
        {
            if(i%factor[j] == 0)
            {
                check = 0;
                break;
            }
            else if(sqr < factor[j])
                break;
        }
        if(check)
        {
            factor[total_factor] = i;
            total_factor++;
        }
        i=i+4;
    }
    while(scanf("%d",&n)==1)
    {
        check = 0;
        for(i=0;factor[i] <= n;i++)
        {
            for(j=0;(n%factor[i])==0;j++)
                n = n / factor[i];
            if(j>0)
            {
                if(check!=0)
                    printf(" * ");
                printf("%d",factor[i]);
                if(j>1)
                    printf("^%d",j);
                check=1;
            }
        }
        printf("\n");
    }   
    return 0;
}

http://zerojudge.tw/ShowProblem?problemid=a010