一個數字若存在大于平方根的因數必然會對應一個小于平方根的因數通俗講解 直白例子核心一句話一個正數如果能被整除除了 1 和自己一定會有一個因數 ≤ 它的平方根所以我們不用一直循環(huán)到數字一半查到平方根就足夠判斷了。舉最簡單的例子數字 1616 的平方根 4 16 所有成對因數 1 × 16 2 × 8 4 × 4規(guī)律 每一組都是「小數 × 大數」 左邊數字全都 ≤ 4平方根右邊全都 ≥ 4。 只要 2、3、4 都不能整除 16那后面的 8、16 壓根不用看肯定也無法整除。例子 1判斷 15 是不是質數15 平方根≈3.87我們只需要循環(huán) 2、315 ÷ 2 不能整除15 ÷ 3 5可以整除 直接判定不是質數 不用循環(huán)到 15//27原本要循環(huán) 2~7大幅減少次數例子 2判斷 17質數17 平方根≈4.12只循環(huán) 2、3、417%2≠017%3≠017%4≠0 全部除不盡 → 17 是質數 原本要循環(huán)到 8指的是17//2現在只循環(huán) 4 次效率翻倍反例驗證合數 21平方根≈4.58循環(huán) 2、3、4 21 ÷ 3 7直接判定合數 對應的配對3 × 7 3 小于平方根7 大于平方根 只要找到了小的因數大的因數必然存在沒必要往后遍歷總結規(guī)律任意合數 N 一定滿足a × b Na≤b 必然a ≤ √N所以遍歷到平方根就能窮盡所有小因數足以判定質數。