素数的判定

一个数字若存在大于平方根的因数，必然会对应一个小于平方根的因数

通俗讲解 + 直白例子

核心一句话

一个正数如果能被整除（除了 1 和自己），一定会有一个因数 ≤ 它的平方根，所以我们不用一直循环到数字一半，查到平方根就足够判断了。

举最简单的例子：数字 16

16 的平方根 = 4 16 所有成对因数： 1 × 16 2 × 8 4 × 4

规律： 每一组都是「小数 × 大数」 左边数字全都 ≤ 4（平方根），右边全都 ≥ 4。 只要 2、3、4 都不能整除 16，那后面的 8、16 压根不用看，肯定也无法整除。

例子 1：判断 15 是不是质数

15 平方根≈3.87，我们只需要循环 2、3

• 15 ÷ 2 不能整除
• 15 ÷ 3 = 5，可以整除 直接判定：不是质数 不用循环到 15//2=7（原本要循环 2~7），大幅减少次数

例子 2：判断 17（质数）

17 平方根≈4.12，只循环 2、3、4

• 17%2≠0
• 17%3≠0
• 17%4≠0 全部除不尽 → 17 是质数 原本要循环到 8（指的是17//2），现在只循环 4 次，效率翻倍

反例验证：合数 21

平方根≈4.58，循环 2、3、4 21 ÷ 3 = 7，直接判定合数 对应的配对：3 × 7 3 小于平方根，7 大于平方根 只要找到了小的因数，大的因数必然存在，没必要往后遍历

总结规律

任意合数 N 一定满足：a × b = N（a≤b） 必然：a ≤ √N所以遍历到平方根，就能穷尽所有小因数，足以判定质数。