Why we dont have to check if the number is prime when getting prime factors?

Question

This is a typical code to find prime factors:

public static List<Integer> primeFactors(int numbers) {
    int n = numbers;
    List<Integer> factors = new ArrayList<Integer>();
    for (int i = 2; i <= n / i; i++) {
      while (n % i == 0) {
        factors.add(i);
        n /= i;
      }
    }
    if (n > 1) {
      factors.add(n);
    }
    return factors;
  }

My question is why don't we check if i is prime or not before adding it to the list?

Answer 1

We can do a proof by contradiction to show that that can't happen.

Imagine that some composite number gets added to the list. There must be some smallest composite number that's added to the list. Let's call it c, and imagine that its smallest prime factor is p. We know that p < c, so the loop must have run with p before it ran with c. When the loop did run with p, we know that the loop would find p as a divisor of the number n, because p is a divisor of c and c is a divisor of n. But after doing this, the code would have updated n by dividing out all copies of p. That means that when we got to the part where the loop ran on the number c, the number c wouldn't divide n any more because p divides c, but p does not divide this new value of n (remember, we divided out all copies of p). Therefore, c wouldn't have been added to the list - a contradiction!