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題庫目錄
回首頁