階乘的質因數分解-ACM 160

表示階乘的其中一種方法是去紀錄每一個質因數出現的頻率。例如 825 這個值, 可以用數字序列 (0 1 2 0 1), 來表示 0 個 2, 1 個 3, 2 個 5, 0 個 7, 1 個 11。寫一個程式讀入一個數字 N (2<=N<=100), 算出階乘結果，以之前的方式來表示這個階乘。

直覺的做法是先算出階乘，再求質因數分解，但即使是使用long long也無法算出100!，因為會overflow，那如果分開求質因數分解，如100!=100*99*98*.....*1，先算100的質因數分解，然後99， 依此類推，最後再統計起來就可以了，似乎是可行的，但其實還有一個偷雞的方法，先建一個質數表，然後用每個質數去代，例如我們先來觀察10!的2質因數個數要怎麼算，10!=10*9*8*7*6*5*4*3*2*1，其中2, 4，6，8 ，10可以被2整除，4，8可以被2^2整除，8可以被2^3整除，所以2的資因數個數等於5+2+1=8，可以寫成以下的演算法。

1.     int prime_factor_count = 0;
   
2.     int d = 0;
   
3.     for(i=0; i<PRIME_TABLE_SIZE&& prime_table[i] <= n; ++i){
   
4.         d = prime_table[i];
   
5.         while(d <= n){
   
6.             prime_factor_count += n/d;
   
7.             d *= prime_table[i];
   
8.         }
   
9.         cout<<"Number of times of prime "<<prime_table[i]<<"is "<<prime_factor_count<<endl;
   
10.         prime_factor_count = 0;
    
11.     }

複製代碼

如此一來要求解100!的質因數分解也是瞬間的事而已。

...

瀏覽完整內容，請先 註冊 或 登入會員