For this code, which finds the prime factors of integer n, why does the loop's integer 'i' should repeat until 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;
}

CodePudding user response：

If you follow the algorithm yourself, you would notice that once you go to a number that high, you will already have found every prime factor.

CodePudding user response：

Looping until