Problem 3: Largest Prime Factor

Q. What is the largest prime factor of the number 600851475143 ?


Sol:
It can be seen that the largest prime factor of a number is equal to larger of its largest prime factor of its largest factor and the smallest factor.
i.e. largest prime factor(n)=max(smallest factor(n), largest prime factor(largest factor(n)))
or,largest prime factor(n)=max(smallest factor(n), largest prime factor(n/smallestfactor(n)))


using the relation, either the recursive or the iterative approach can be applied to solve the problem..


Now, it can also be seen that while finding the smallest factor, we only need to divide the number concerned by only one even number '2' and rest can be odd numbers. So, all the other even numbers can be eliminated from the process, thus optimizing our program. 
Since, a factor 'i' can divide 'n' multiple times, we can also put a subroutine to divide n by i multiple times until the new number comes out to be not divisible by i, further optimizing the problem...


Now the last and the easiest part , Coding :



long long int solution(long long n)
{

     int i=2;
     long long x;
     if(n%2==0)
     {
               x=n/i;
               while(x%i==0)
                            x=x/i;
               x=solution(x);
               return((i>x)?i:x);
     }
     else
     {
         i=3;    
         while(i < sqrt ( ( double ) n ) )
         {
                                 if(n%i==0)
                                 {
                                           x=n/i;
                                           while(x%i==0)
                                                        x=x/i;
                                           x=solution(x);
                                           return((i>x)?i:x);
                                 }
                                 i=i+2;
         }
         return n;
     }
}



As explained above, the code applies recursive approach to solve the problem and returns the largest prime factor for 'n'..

Please post your comments and doubts...

Better algorithms are always welcome..