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 :-)

Project Euler 2

Problem #2:Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

Solution: A straight forward implementation in C for this problem can be as shown

#include
#define LIMIT 4000000
int main()
{
 long a=1, b=2, c=0, sum=0;
 sum = b;
 while(c < LIMIT ){
  c = a+b;
  if(c < 1000000)
  if(c%2 == 0)
   sum += c;
  a = b;
  b = c;
 }
 printf("\nAnswer to euler #2 : %ld\n",sum);
}

        
                 This code works fine for our required need, but more optimizations can be done.How? Lets look at the fibo seq.

                                                    1 1 2 3 5 8 13 21 34 55 89 144 ...

                 As we can see,every 3rd term is a even number. Therefore we can change the code accordingly to just sum up every third number.
                 Another approach is we can find a recurrence funtion for this new series i.e. we can have :

F`(n)=4*F`(n-1) + F`(n-2)

It is easy to prove that for Fibonacci series we get:

 F(n)=4*F(n-3)+F(n-6) 

Thus we get a more faster running code, which we eventually need :-)

Enjoy coding :-)

My all time favourite Movies

Mughal-e-azam

A Wednesday

Munnabhai M.B.B.S

Swades - we the people

Dil Chahta Hai

Rang De Basanti

Project Euler 1

Problem #1. Add all the natural numbers below one thousand that are multiples of 3 or 5.

Solution : This can be done in two ways ....

i. The normal method, i.e. run a for from 1 to 1000 and check for the given condition on each number.

This method does solves our problem but is crude.

upperlimit=999
total_sum=0
for i=1 to upperlimit do
if (i mod 3=0) or (i mod 5)=0 then
total_sum:=total_sum+i;
output total_sum

ii. The short-cut method : In this you need only one formula and just need to compute value of 3 expressions.

Just go through---->

The solution to given problem will be the answer of this expression :

ans = sumDivisibleBy(3) + sumDivisibleBy(5) - sumDivisibleBy(15)

Now for n=3 :

3,6,9,12,15,18,21,24,27,.....,999 = 3(1,2,3,4,5,6,7,8,9,....,333)

Now we know that :

1 + 2 + 3 + .... + q = 1/2*q*(q+1)

In our case : q = upperlimit / n

Therefore our solution says :

Function sumDivisibleBy(n):
q = upperlimit div n
return n*(q*(q+1)) div 2
EndFunction

print sumDivisibleBy(3)+sumDivisibleBy(5)-sumDivisibleBy(15)

Feel free to ask any kind of querry, I'll try my best to solve it.

Enjoy coding :-)

The Month of Purity and Patience

Ramzaan is the month of purity and patience that brings the human soul towards the Creator and makes him think about each and every small and wonderful things He has created. Fasting reschedules all your daily routines that we disturbed otherwise.

---------------------------------------------------------
Take account of yourself before you are called for account.

Bubble vs Quick Sort

A good comparision between Bubble Sort and Quick Sort.

Please Wait while the video loads.......