Project Euler #3 - C

Question:
The prime factors of 13195 are 5, 7, 13 and 29.


What is the largest prime factor of the number 600851475143 ?


Solution:
We are going to assume that a list of prime numbers is NOT available to solve this problem. Still, this question is simple as long as you know one basic law of mathematics: all composite numbers can be written as a product of primes. I'm going to omit the proof (by contradiction) and ask you to just trust me on this. For example,


8 = 2*2*2 
9 = 3*3 
10 = 2*5 
147 = 3*7*7

So now with that little nugget tucked away we can tackle this problem. The solution is to loop through 2 and every odd integer and check whether the integer divides evenly into our subject number. If it does, divide the subject by that integer repeatedly until a remainder is found. Once a remainder is found, continue on to the next integer. Finally, we stop looking for a new integer when our subject equals 1. 


You might be thinking, "wait, does that really work?" I assure you, it does. Let's look at our previous examples.


Subject: 8
Integer: 2


Iteration 1: Does 2 divide 8? Yes, so divide 8 by 2.
Iteration 2: Does 2 divide 4? Yes, so divide 4 by 2. 
Iteration 3: Does 2 divide 2? Yes, so divide by 2. 
Iteration 4: Does 2 divide 1? Nope!... subject equals 1. 
Highest prime that divides 8 is 2.  
   
Subject: 147
Integer: 2


Iteration 1: Does 2 divide 147? No, increase Integer. 
Iteration 2: Does 3 divide 147? Yes, so divide by 3. 
Iteration 3: Does 3 divide 49? No, increase Integer.
Iteration 5: Does 5 divide 49? No, increase Integer. 
Iteration 7: Does 7 divide 49? Yes, so divide by 7. 
Iteration 8: Does 7 divide 7? Yes, so divide by 7.
Iteration 9: Does 7 divide 1? No. Subject equals 1. 
Highest prime that divides 147 is 7. 

This algorithm works for ALL numbers. So without further adieu, my solution. With all this in mind, I do not believe my code needs any further explanation.


#include <stdio.h>


int main (void)
{
long long current = 600851475143; 
int i = 3; // start at 3 for primes... we can do this since subject is ODD
int high = 0;


while (1)
{
while (!(current % i)) // while no remainder
{
current /= i;  // divide and replace
high = i; 
}

if (current == 1)
break;


i +=2 ; // skip all even numbers since not prime
}


printf ("Highest prime factor of 600851475143 is %d\n", high);
return 1;
}

Compile and see the answer appear before your eyes.