主題

ZeroJudge - d131: 00160 - Factors and Factorials 解題心得

Not In My Back Yard | 2021-02-23 22:44:38

題目連結:


題目大意:
輸入有多列,每列給定一正整數 N (2 ≦ N ≦ 100),請質因數分解 N! (N 階乘)。

輸出以等號右方第一個數字代表第一小質因數之次方、第二個數字代表第二小質因數之次方,以此類推。每個輸出的數字固定佔三格字元並靠右對齊。每列輸出最多 15 個質因數,剩下的換行輸出並對齊於等號,格式參見範例輸出。



範例輸入:
5
53
0


範例輸出:
  5! =  3  1  1
53! = 49 23 12  8  4  4  3  2  2  1  1  1  1  1  1
        1


解題思維:
先利用埃式篩法(如這題)將 ≦ 100 的質數全數找出。

然後每輸入一個 N 值,由小到大掃過剛剛建立的質數表,對於每個質數 p 去看看 N! 含有 p 的多少次方,而該值為
floor(N ÷ p) + floor(N ÷ p ^ 2) ……
找到後,先判斷現在這個 p 是第幾個質因數。如果是第 16 、 31 個等等,請先換行。

之後便可以直接輸出該值(記得按照格式,每個數字佔三格,且要靠右對齊)。




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

創作回應

相關創作

更多創作