质因数分解算法中循环终止条件设置为i*i<=n的原因是什么

给出的代码如下：

vector<int> factor(int n) {
    vector<int> ret;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ret.push_back(i);
            n /= i;
        }
    }
    if (n > 1) ret.push_back(n);
    return ret;
}

将循环终止条件设为i * i <= n的原因如下：

• 核心依据是质因数的数学性质：对于任意正整数n，如果它是合数，那么一定存在至少一个小于等于√n的正因数。反过来讲，如果我们遍历到√n都没有找到能整除n的数，那么此时的n必然是质数，不需要再继续向后遍历。代码最后的if(n>1) ret.push_back(n)逻辑专门用来处理剩下的这个质数，不会遗漏结果。
  举个例子辅助理解：比如输入n=28，原始√28约等于5.3，i遍历到2的时候，28反复除以2得到n=7，此时i递增到3，3*3=9>7，循环直接终止，剩下的7是质数，通过后续的if判断加入结果即可，不需要再遍历到7。
• 大幅降低算法时间复杂度：如果把终止条件改成i <= n，算法时间复杂度会从O(√n)退化到O(n)，当n数值很大时性能差异非常显著：比如n为1e6时，原逻辑只需要循环1000次，改成i <= n就要循环1e6次，效率差了1000倍。
• 这里的判断条件是和动态变化的n比较，不是和原始输入的n比较：每次找到质因数后都会把n除以该因数，所以实际循环的上限会比原始n的平方根更小，进一步提升了运行效率。

内容的提问来源于stack exchange，提问作者MinKwon Kim