Project Euler #3

Problem #3:Find the largest prime factor of a composite number.

Solution: 
As usual firstly the straight forward implementation. Run a loop and go on checking whether it divides the given number and check if it is prime, storing the largest one.

#include

#include"prime.h" //My own module,code not shown here

int main(){

long long num=600851475143L;

long largest_prime_factor=0,i;

for(i=10;i<num/2;i++)

if(num%i==0)

if(isPrime(i)) //return true if prime

largest_prime_factor=i;

printf("Answer to Euler #3 : %ld",largest_prime_factor);

return 0;

}

                    This can be optimized a little by defining a new upper bound for the loop counter  and that would be square root of the given number.

                     More over 2 is a factor which if checked separately will make our life easy. Then we can increase the factor by step of 2.

                    A little more optimized algorithm is:

n="a large number"



if n mod 2=0



then



    n=n / 2



    lastFactor=2



    while n % 2=0



        n=n / 2



else



    lastFactor=1





    factor=3



    while n>1



         if n % factor=0



         then



                n=n / factor



         lastFactor=factor



         while n % factor=0



                n=n / factor



         factor+=2





output lastFactor

This is not the fully optimized solution but can be modified further. That left to you ;-)

Enjoy coding :-)