Why should the loop repeat until i*i<=n for prime factorization?

Question

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;
}

what is the maximum value of a prime factor of N....it's Sqrt(n) so a faster loop is for (int i = 2; i < Sqrt(n); i++) — Mitch Wheat, Nov 07 '21 at 06:47
@MitchWheat that statement needs to be revised. 10 has prime factor 5 which is greater that sqrt(10). — Albin Paul, Nov 07 '21 at 06:50
Does this answer your question? [Why do we check up to the square root of a prime number to determine if it is prime?](https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr) — Evg, Nov 07 '21 at 06:58

score 1 · Answer 1 · answered Nov 07 '21 at 06:59

1

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.

answered Nov 07 '21 at 06:59

Kneecaps

92
8

Only if you add `i` ***and*** `n / i`. – paxdiablo Nov 07 '21 at 07:03
@paxdiablo, `n / i` might not be prime. And if it is, it is accounted for by the division `n /= i` and the push of the resulting `n` after the loop has finished. – trincot Nov 07 '21 at 09:41

score 1 · Answer 2 · answered Nov 07 '21 at 07:39

Looping until ²> is the same as looping until >√, and this is enough, because there can't be a factor with √<<. Here is a proof:

If there were such a factor , then / is also a factor. That would be a smaller factor (/< because we said √<). But any smaller factor was already a previous value of , and so that factor was already taken out of (by the division we have in the code).

This is a contradiction, and so there is no factor with √<<. The only factor that remains is itself, which is dealt with after the loop.

Why should the loop repeat until i*i<=n for prime factorization?

2 Answers2