Problem10392 Factoring Large Numbers，因數分解

Problem 10392 是一題將 long long int 長整數型態的數做因數分解的題目。

此題要將 30980 之內的質數找出來就夠用了，如果數大於 30980，再用這些質數的次方看找不找的到。以下是找質數 makeprime() 以及 isprime(long long int n) 判斷質數的函式，C 語言程式碼如下：

int makeprime(){
    int i, j;
   
    for(i = 3; i <= MAXSIZE; i += 2)
        if(!prime[i]){
            for(j = i + i; j <= MAXSIZE; j += i)
                prime[j]=1;
            prime_table[prime_table_len ++]=i;
        }
}

int isprime(long long int n){
    int i,temp;
    if(n == 2) return 0;
    if(n % 2 == 0) return 2;
    if(n <= MAXSIZE){
        if ((1-prime[n])) 
           return 0;
    }

    for(i = 0;i != prime_table_len && prime_table[i] * prime_table[i] <= n; ++ i)
        if(n % prime_table[i] == 0)
            return prime_table[i];
    return 0;
}

再來用一遞迴函式將傳入的值印出因數，C 語言程式碼如下：

void printFactors(long long int n)
{
     long long int i;
     if (n != 1 && n != 0)
        i = isprime(n);
     else return;
     if(i)
         printf("%s%lld\n", "    ", i), printFactors(n/i);
     if (!i && n != 1) printf("%s%lld\n", "    ",n);    
     return;
}

最後，主程式只須這樣呼叫：

makeprime();
long long int n, i;
while (1)
{
    scanf("%lld", &n);
    if (n < 0) break;
    printFactors(n);
    printf("\n");
}

By David.K

p10392題目連結
回ACM題庫目錄
回首頁