主題

ZeroJudge - e912: n! 的因數分解　解題心得

Not In My Back Yard | 2020-03-12 00:11:16 | 巴幣 2 | 人氣 297

題目連結：

e912: n! 的因數分解

題目大意：

輸入有多列，每列給定一正整數 n （1 ＜ n ≦ 10000）。求 n! （即 n 階層＝ n × (n － 1) × …… × 1）的質因數分解之式子。

範例輸入：

6

9

範例輸出：

6! = 2^4 * 3^2 * 5^1

9! = 2^7 * 3^4 * 5^1 * 7^1

解題思維：

建一個質數表。接著對於每個輸入的 n 值，跑過一次所有不大於 n 的質數 p 並計算 1 ～ n 之間有多少是 p 的倍數、p ^ 2 的倍數、p ^ 3 的倍數……個數分別是 floor(n ÷ p)、floor(n ÷ (p ^ 2))、floor(n ÷ (p ^ 3))、……其中 floor 函式代表下高斯函數，在正整數值域等同於無條件捨去。

將那些倍數加起來即是 n! 裡質數 p 所佔有的次方數。把所有的小於等於 n 的質數求出各自的次方值即為所求。

當然，除了每輸入一個 n 值才做一次。可以預先做完所有可能的 n 值之結果。之後輸入什麼就輸出原先求得的結果即可。也就是建表。

本人的程式碼（於 CodePile 上）（這個有建表）

本人的程式碼（於 CodePile 上）（這個沒建表）

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。