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


lawrence910426@gmail.com (l4wr3nc3)

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)

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)

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