According to topcoder Link, We need to compute till square root of number to list its all prime factors... Now I am able to prove in the following code that we are doing right till we are in the for loop.. But I am unable to figure out why the remaining number will be prime i.e. after we go out of the loop that if (n > 1) printf("%d",n); is what is troubling me ..! Can you please give me a formal proof along with examples....
void factor(int n)
{
int i;
for(i=2;i<=(int)sqrt(n);i++)
{
while(n % i == 0)
{
printf("%d ",i);
n /= i;
}
}
if (n > 1) printf("%d",n);
printf("\n");
}
Initially the process proceeds to search for the smallest factor of n smaller than its square root.
If it doesn't have one, then n is prime. So print out n as it's one smallest prime factor!
If you find a smallest factor then it must be prime. If not, it's composite and has a smaller prime factor - contradiction.
Having found the smallest prime factor divide n by that factor to eliminate it (remember it may be that n == i*i*i*...i*r where i is the prime factor and r the residue). That's what is happening inside the while(n%i==0) loop.
At the end of that we have n holding that residue.
So now we want the smallest prime factor of r.
We know that smallest prime factor will be i. Why? Because if r had a smaller prime factor than i then i isn't the smallest prime factor of n.
So we can proceed to search i+1 to sqrt(r) by trial divisions of r to find the next smallest prime factor of n. If we don't find any and r>1 then r is the last prime factor.
Proceed by induction.
After each round of elimination (go inside the while(n%i==0) loop) we have a number we know to have no prime factors <=i.