#18866: 解題思考路線


lawrence910426@gmail.com (l4wr3nc3)

School : 新北市立板橋高級中學
ID : 67988
IP address : [118.167.4.40]
Last Login :
2019-12-01 23:05:13
a121. 質數又來囉 | From: [1.161.43.194] | Post Date : 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)

School : 新北市私立南山高級中學
ID : 93041
IP address : [118.166.49.165]
Last Login :
2020-04-02 16:15:04
a121. 質數又來囉 | From: [118.166.61.10] | Post Date : 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 (reversed(稱暱開公))

School : 臺北市立大安高級工業職業學校
ID : 74619
IP address : [1.168.17.106]
Last Login :
2020-01-23 11:23:07
a121. 質數又來囉 | From: [220.135.132.138] | Post Date : 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