2008年2月12日 星期二

Problem 160 Factors and Factorials,因數與階乘

我喜歡這輸入值的限制,居然是 2 到 100。
這題是說一種特大數字的表示方法,就是用其質因數的次數來表示。這裡應用的範圍是 2 到 100的階乘值。
經過小小的計算,我先把100以內的質數算出來,然後宣告一個質數的陣列,如下
int prime[25] = {2,3,5,7,11,13,17,19,23,29,31,37,41,
43,47,53,59,61,67,71,73,79,83,89,97};

接下來計算所有 2 到 100每個數的質因數表示方法,也就是說,每個數字都有一個質因數的陣列表示方法,這個資料在後來處理階乘時,只要將階乘中乘數的每個質因數陣列相加,答案就出來了。
    int primeTable[101][25]={0};
for (i=2;i<=100;i++)
{
k = i;
j=0;
while (k>=2)
{
if (k%prime[j]==0)
{
primeTable[i][j]++;
k /= prime[j];
}
else
j++;
}
}

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

沒有留言: