为什么查找一个数的质因数只需遍历到其sqrt(number)即可？

核心逻辑完全来自正整数因数的成对性质，没有复杂的高阶定理：

• 对任意大于1的正整数n，它的因数一定是成对存在的：如果d是n的因数，那么一定存在整数k = n/d，满足d * k = n，k同样是n的因数。
• 任意一对因数(d, k)不可能同时大于√n。用最基础的反证法就能验证：如果d > √n且k > √n，那么两者的乘积d*k > √n * √n = n，和d*k = n的基本定义矛盾。也就是说，任何一个因数对里，必然至少有一个数小于等于√n。

很多人会疑惑：如果n有一个比√n大的质因数，难道不会漏吗？其实不会，因为常规质因数分解算法不是单纯遍历找原数的因数，而是边遍历边把已经找到的质因数从当前待分解的数里除干净：

1. 从2开始从小到大试除，每找到一个能整除当前数的质数，就把这个质因数记下来，同时把当前数里所有这个质因子的幂次全部除尽；
2. 等遍历到最初设定的√n（更高效的实现会动态更新为当前待分解数的平方根）时，如果剩下的待分解数大于1，那这个数本身一定是个质数——它不可能是合数，因为如果它是合数，它的质因子肯定小于等于它自己的平方根，也就必然小于等于最开始的√n，早就在之前的遍历过程中被除干净了，根本不可能留到最后。

举个最直观的例子：分解n=202，√202≈14.2，只需要遍历2到14即可：

• 试2：202÷2=101，记录质因数2，当前待分解数变成101；
• 接着试3到14的所有整数，没有能整除101的数，遍历结束；
• 此时剩下的101>1，直接记为质因数即可，不需要额外遍历到101。最终质因数分解结果是2×101，完全正确。

常见误区提醒：如果算法只是死板遍历2到√n找原数的整除项，全程不剔除已找到的质因数，那确实会漏掉大于√n的质因数，但这是算法实现的问题，不是原理的问题。常规分解算法的边找边除逻辑，刚好利用因数成对的性质覆盖了所有可能的质因数。

内容的提问来源于stack exchange，提问作者Rahul Tiwari