一个数字若存在大于平方根的因数必然会对应一个小于平方根的因数通俗讲解 直白例子核心一句话一个正数如果能被整除除了 1 和自己一定会有一个因数 ≤ 它的平方根所以我们不用一直循环到数字一半查到平方根就足够判断了。举最简单的例子数字 1616 的平方根 4 16 所有成对因数 1 × 16 2 × 8 4 × 4规律 每一组都是「小数 × 大数」 左边数字全都 ≤ 4平方根右边全都 ≥ 4。 只要 2、3、4 都不能整除 16那后面的 8、16 压根不用看肯定也无法整除。例子 1判断 15 是不是质数15 平方根≈3.87我们只需要循环 2、315 ÷ 2 不能整除15 ÷ 3 5可以整除 直接判定不是质数 不用循环到 15//27原本要循环 2~7大幅减少次数例子 2判断 17质数17 平方根≈4.12只循环 2、3、417%2≠017%3≠017%4≠0 全部除不尽 → 17 是质数 原本要循环到 8指的是17//2现在只循环 4 次效率翻倍反例验证合数 21平方根≈4.58循环 2、3、4 21 ÷ 3 7直接判定合数 对应的配对3 × 7 3 小于平方根7 大于平方根 只要找到了小的因数大的因数必然存在没必要往后遍历总结规律任意合数 N 一定满足a × b Na≤b 必然a ≤ √N所以遍历到平方根就能穷尽所有小因数足以判定质数。
一个数字若存在大于平方根的因数必然会对应一个小于平方根的因数通俗讲解 直白例子核心一句话一个正数如果能被整除除了 1 和自己一定会有一个因数 ≤ 它的平方根所以我们不用一直循环到数字一半查到平方根就足够判断了。举最简单的例子数字 1616 的平方根 4 16 所有成对因数 1 × 16 2 × 8 4 × 4规律 每一组都是「小数 × 大数」 左边数字全都 ≤ 4平方根右边全都 ≥ 4。 只要 2、3、4 都不能整除 16那后面的 8、16 压根不用看肯定也无法整除。例子 1判断 15 是不是质数15 平方根≈3.87我们只需要循环 2、315 ÷ 2 不能整除15 ÷ 3 5可以整除 直接判定不是质数 不用循环到 15//27原本要循环 2~7大幅减少次数例子 2判断 17质数17 平方根≈4.12只循环 2、3、417%2≠017%3≠017%4≠0 全部除不尽 → 17 是质数 原本要循环到 8指的是17//2现在只循环 4 次效率翻倍反例验证合数 21平方根≈4.58循环 2、3、4 21 ÷ 3 7直接判定合数 对应的配对3 × 7 3 小于平方根7 大于平方根 只要找到了小的因数大的因数必然存在没必要往后遍历总结规律任意合数 N 一定满足a × b Na≤b 必然a ≤ √N所以遍历到平方根就能穷尽所有小因数足以判定质数。
