#16575: 觀念


freedom501999@gmail.com (帥氣魔方生)

學校 : 不指定學校
編號 : 88611
來源 : [39.8.203.54]
最後登入時間 :
2019-05-30 22:56:25
b369. [福州19中]因子和阶乘 -- 福州十九中 | From: [110.28.110.140] | 發表日期 : 2019-01-15 22:49

這題是算 1 ~ n 中所出現過的質數個數,因為 n 最大到 30000,所以必須先建立質數表共 3246 個
( 為了避免迴圈中出現 " 除以 0 ",找到小於 30000 的最大質數後要再多找一個 )
至於找法,以 10!為例如下:
1. 首先第一個質數是 2 ,1 ~ 10 中是 2 的倍數的數字共有 10 / 2 = 5 個 ( 2 4 6 8 10 )
    這代表因數中含有一個 2 的數字個數;接著將這個數字再除以 2 ,5 / 2 = 2 
    這意思是因數中含有兩個 2 的數字個數,也就是 2^2 = 4 的倍數,因為這些數可以拿出第二個 2 ;
    最後將這個數字再除以 2 ,2 / 2 = 1 ,代表因數中含有三個 2 的數字個數 ( 8 的倍數 ),因為這些數可以提出第三個 2
    所以 10!質因數分解後一共有 5 + 2 + 1 = 8 個 2
2. 接著是第二個質數是 3,同上述操作,10 / 3 = 3、3 / 3 = 1 ,所以一共有 3 + 1 = 4 個 3 
    ( 除法只取整數的商 )
3. 依此類推,5 的個數為 2,7 的個數為 1,所以此題輸出結果為:
    10!=8 4 2 1
所以此題依上述原理,即可輕鬆解題
至於具體實作,用 迴圈
 
ZeroJudge Forum