#31085: 避免 超時的辦法!有效版


Dhomos (dhomos)

學校 : 臺北市立和平高級中學
編號 : 194637
來源 : [59.115.217.33]
最後登入時間 :
2022-08-10 06:11:07
a121. 質數又來囉 | From: [59.115.172.14] | 發表日期 : 2022-07-10 13:23

除了直觀的 看(2~n-1)有沒有其他因數

使用其他判斷質數方法:

  1. 質數n除了是 2 和 3 以外, n 除以 6 一定是餘 1 或是 5

      即 n = 6a+1 or 6a+2 

     但是!不是任何數除以6餘 1 或是 5 就是質數 ex.35 49 (大家想一下)

     先用這個進行判斷 時間就會省很多

 

    2. > 根據埃拉斯特尼篩法 :若n是合數,其必定會有至少一個因數 <= n^0.5

       質數檢驗能不能整除 迴圈不用一定要試到n-1        

       開根號後 迴圈次數又少很多次

 

質數檢驗方法 可參考:https://magiclen.org/prime-number/

運用以上兩個方法來加入你的判斷 就能順利通過不超時囉~~

 
ZeroJudge Forum