#45296: 質數篩法題


sam851015@gmail.com (多挖鼻孔有益身心健康)

學校 : 臺中市立惠文高級中學
編號 : 277705
來源 : [123.192.228.253]
最後登入時間 :
2025-05-10 17:41:09
c050. 00453 - Goldbach's Conjecture -- UVa543 | From: [123.192.228.253] | 發表日期 : 2025-02-08 12:34

首先,正確的 UVa 題號應該是 543 而非 453,如果你想去 UVa 玩的話別跑錯地方

 

先用質數篩法建一個從 3 到 1000000 的質數表

不需要考慮 2,因為 2 不是奇數的質數

(你如果想從什麼地方直接複製貼上過來也不是不行......一共有 78497 個質數,給你參考)

 

然後窮舉,數字一個一個試

跑一個 for 循環遍歷質數表,將讀到的數紀錄為 a ,表示第一個質數

另一個數 b = n - a

最後檢查 b 是不是質數就可以了

 

不建質數表也行,但應該會 TLE

至少...我用 6n±1 搭配 Miller Rabin 吃 TLE 了

 

 
ZeroJudge Forum