發表新討論
#18866: 解題思考路線


lawrence910426@gmail.com (l4wr3nc3)

學校 : 新北市立板橋高級中學
編號 : 67988
來源 : [140.114.6.181]
最後登入時間 ：
2020-11-09 14:57:43
a121. 質數又來囉 | From: [1.161.43.194] | 發表日期 : 2019-08-09 23:56

先備知識

- Linear Sieve

- Eratosthenes sieve

連結: http://www.csie.ntnu.edu.tw/~u91029/Prime.html

 

############ 正文 ############

對於任意正整數 N，若 N 在 [2,sqrt(N)] 中沒有任何因數，則 N 必為質數

因此，建 Prime Table 到 Sqrt(10^8) 

並且使用 Eratosthenes sieve 將 [l,r] 中的合數打掉

最後再找出有幾個質數即可

 

############ 備註 ############

- a,b 有可能為 a>b 或是 a<b 作者陰我們，幫QQ

- 那些 top coder 是不是都用黑魔法建質數表啦><

 

 

 
#18870: Re:解題思考路線


rexwu1104@gmail.com (黑雪公主 Black Lotus)

學校 : 新北市私立南山高級中學
編號 : 93041
來源 : [49.216.131.103]
最後登入時間 ：
2024-06-06 19:28:43
a121. 質數又來囉 | From: [118.166.61.10] | 發表日期 : 2019-08-10 11:20

先備知識

- Linear Sieve

- Eratosthenes sieve

連結: http://www.csie.ntnu.edu.tw/~u91029/Prime.html

 

############ 正文 ############

對於任意正整數 N，若 N 在 [2,sqrt(N)] 中沒有任何因數，則 N 必為質數

因此，建 Prime Table 到 Sqrt(10^8) 

並且使用 Eratosthenes sieve 將 [l,r] 中的合數打掉

最後再找出有幾個質數即可

 

############ 備註 ############

- a,b 有可能為 a>b 或是 a

- 那些 top coder 是不是都用黑魔法建質數表啦><

 

 

只是因為現在系統慢


 
#19776: Re:解題思考路線


az.rejoice@gmail.com (Icy)

學校 : 臺北市立大安高級工業職業學校
編號 : 74619
來源 : [134.208.41.3]
最後登入時間 ：
2024-03-18 01:01:11
a121. 質數又來囉 | From: [220.135.132.138] | 發表日期 : 2019-10-29 21:35

先備知識

- Linear Sieve

- Eratosthenes sieve

連結: http://www.csie.ntnu.edu.tw/~u91029/Prime.html

 

############ 正文 ############

對於任意正整數 N，若 N 在 [2,sqrt(N)] 中沒有任何因數，則 N 必為質數

因此，建 Prime Table 到 Sqrt(10^8) 

並且使用 Eratosthenes sieve 將 [l,r] 中的合數打掉

最後再找出有幾個質數即可

 

############ 備註 ############

- a,b 有可能為 a>b 或是 a

- 那些 top coder 是不是都用黑魔法建質數表啦><

 

 

這題使用Segmented Sieve會快很多，尤其是當測資在相近大數字之間時



 
ZeroJudge Forum