#20590: 用質數 篩法
jason680@gmail.com
(jason lee)
學校
:
不指定學校
編號 : 115025
來源 : [220.129.73.59]
最後登入時間 ：
2021-08-05 01:38:13
a121. 質數又來囉
| From: [61.228.232.123] |
發表日期
:
2020-02-11 10:57
用質數 篩法 舉例: 找23到30中的質數(數量) 23, 24, 25, 26, 27, 28, 29, 30 偶數一定不是質數,所以建表就直接跳過 (為了說明對齊, 只接用 個位數表示) 3, 4, 5, 6, 7, 8, 9, 0 <== 說明對齊用 23-30 1, 0, 1, 0, 1, 0, 1, 0 <==建表(偶數直接去除) 說明: 0 表是不是質數, 1(可能)是質數 ------------------ 30 開根號為 5.xx, 所以 用3跟5 來篩除 不是質數的 表格是從數字23開始, 要先算從那一個index開始篩除 23 %3 = 2, 3-2 = 1 表示從 index = 1 (數字24開始篩除) 23 %5 = 3, 5-3 = 2 表示從 index = 2 (數字25開始篩除) 3, 4, 5, 6, 7, 8, 9, 0 <== 說明對齊用( 23-30) ------------------------------------ 1, 0, 1, 0, 1, 0, 1, 0 <==建表(偶數直接去除) 1, x, 1, 0, x, 0, 1, x <==x 表示本次用3篩除 1, 0, x, 0, 0, 0, 1, x <==x 表示本次用5篩除 1, 0, 0, 0, 0, 0, 1, 0 註: x 是用於說明,實際填0 最後 數一數(或加總)幾個1, 就是有幾個質數了 注意: 質數 篩法觀念很簡單,一個一個篩... 但寫程式要注意 數字很小(1跟2)的處理 數字1 不是質數
#20597: Re:用質數 篩法
a121. 質數又來囉
| From: [122.118.43.201] |
發表日期
:
2020-02-11 19:09
用質數 篩法 舉例: 找23到30中的質數(數量) 23, 24, 25, 26, 27, 28, 29, 30 偶數一定不是質數,所以建表就直接跳過 (為了說明對齊, 只接用 個位數表示) 3, 4, 5, 6, 7, 8, 9, 0 <== 說明對齊用 23-30 1, 0, 1, 0, 1, 0, 1, 0 <==建表(偶數直接去除) 說明: 0 表是不是質數, 1(可能)是質數 ------------------ 30 開根號為 5.xx, 所以 用3跟5 來篩除 不是質數的 表格是從數字23開始, 要先算從那一個index開始篩除 23 %3 = 2, 3-2 = 1 表示從 index = 1 (數字24開始篩除) 23 %5 = 3, 5-3 = 2 表示從 index = 2 (數字25開始篩除) 3, 4, 5, 6, 7, 8, 9, 0 <== 說明對齊用( 23-30) ------------------------------------ 1, 0, 1, 0, 1, 0, 1, 0 <==建表(偶數直接去除) 1, x, 1, 0, x, 0, 1, x <==x 表示本次用3篩除 1, 0, x, 0, 0, 0, 1, x <==x 表示本次用5篩除 1, 0, 0, 0, 0, 0, 1, 0 註: x 是用於說明,實際填0 最後 數一數(或加總)幾個1, 就是有幾個質數了 注意: 質數 篩法觀念很簡單,一個一個篩... 但寫程式要注意 數字很小(1跟2)的處理 數字1 不是質數
超感謝
花了六小時編程加debug
總算AC了
為了得到測資慢慢試也快50次了
結果發現錯在完全沒注意到的地方Orz
ZeroJudge Forum