#38086: 質數判斷優化


jchu0952@gmail.com (胡哥)

學校 : 不指定學校
編號 : 135958
來源 : [163.25.253.206]
最後登入時間 :
2024-03-26 09:13:46
a121. 質數又來囉 | From: [111.251.27.106] | 發表日期 : 2023-10-24 16:08

  1. 對於每個數字 num,首先檢查一些簡單的情況:

    • 如果 num 小於或等於1,它不是質數,返回 false
    • 如果 num 是2或3,它是質數,返回 true
    • 如果 num 可以被2或3整除,它不是質數,返回 false
  2. 對於其他情況,我們可以採用更快速的質數檢查演算法。這個演算法基於以下觀察:

    • 一個數是否是質數,可以用6的倍數兩側的數來判斷。也就是說,我們只需要檢查形如6k ± 1的數,其中k是整數。
    • 如果一個數可以被形如6k ± 1的數整除,那它不是質數。
  3. 我們只需要檢查 num 是否可以被形如6k ± 1的數整除,這可以通過一個迴圈來實現。迴圈從5開始,每次遞增6,檢查兩個數,分別是6k - 1和6k + 1,是否能整除 num

    • 如果其中任何一個數可以整除 num,則 num 不是質數,返回 false
    • 否則,認為 num 是質數,返回 true
    • from chatgpt
 
ZeroJudge Forum