I have the following code for prime factorization.
public static void primeFactors(int n) { for (int i = 2; i <= Math.sqrt(n); i = i+1) { while (n%i == 0) { factors.add(i); n = n/i; } } if (n>2 ) { factors.add(n); } System.out.println(factors); } From a mathematical point of view we have to check if each divisor i is also prime and not only if it is factor. Could anyone explain me (mathematically) why the algorithm still works?
Suppose i is not prime; say i = j * k where j and k are less than i. That means that when our loop reaches i, it has already reached j and k first. And after we did the loop for j, n can no longer be divisible by j since we already factored all the j's out of it. Similarly for k. So when we do the loop for i, we know n can no longer be divisible by either j or k; therefore it cannot be divisible by i. So the while loop is never executed. This means we don't need to make a special check for non-prime i's, because nothing will happen anyway.
