發表新討論
#7301: 減少逾時寫法


believe7028 (四資工一甲_楊承翰)

學校 : 國立高雄應用科技大學
編號 : 29690
來源 : [114.47.134.161]
最後登入時間 ：
2013-06-22 20:53:35
a007. 判斷質數 | From: [1.174.45.153] | 發表日期 : 2012-12-16 13:33
假設輸入最大情況為 2147483647，則只要驗證從 2 開始到 46341 以內的數是否可以整除即可，亦即不管輸入多少，最多檢測 46341 次，假如再加入偶數（不含2）輸入直接判定非質數，且奇數輸入的檢測不檢測偶數因數，則可再減少一半最大可能次數，至於46341的來由，即2147483647開根號得來，所以若輸入為101，則只需要驗證到11。只要使用一次根號減少數目就足以應付這題的逾時了，至於為什麼驗證到輸入開根號內的數字就足夠，請去請教數學老師。 
#7302: Re:減少逾時寫法


believe7028 (四資工一甲_楊承翰)

學校 : 國立高雄應用科技大學
編號 : 29690
來源 : [114.47.134.161]
最後登入時間 ：
2013-06-22 20:53:35
a007. 判斷質數 | From: [1.174.45.153] | 發表日期 : 2012-12-16 13:36
假設輸入最大情況為 2147483647，則只要驗證從 2 開始到 46341 以內的數是否可以整除即可，亦即不管輸入多少，最多檢測 46341 次，假如再加入偶數（不含2）輸入直接判定非質數，且奇數輸入的檢測不檢測偶數因數，則可再減少一半最大可能次數，至於46341的來由，即2147483647開根號得來，所以若輸入為101，則只需要驗證到11。只要使用一次根號減少數目就足以應付這題的逾時了，至於為什麼驗證到輸入開根號內的數字就足夠，請去請教數學老師。


 
ZeroJudge Forum