對於每個數字 num
,首先檢查一些簡單的情況:
num
小於或等於1,它不是質數,返回 false
。num
是2或3,它是質數,返回 true
。num
可以被2或3整除,它不是質數,返回 false
。對於其他情況,我們可以採用更快速的質數檢查演算法。這個演算法基於以下觀察:
我們只需要檢查 num
是否可以被形如6k ± 1的數整除,這可以通過一個迴圈來實現。迴圈從5開始,每次遞增6,檢查兩個數,分別是6k - 1和6k + 1,是否能整除 num
。
num
,則 num
不是質數,返回 false
。num
是質數,返回 true
from chatgpt