Life -- Code -- Experience

March 16, 2011

Experience Bolta hai...

Last semester of engineering really taught me much more than I could perceive.My technical knowledge got boosted but on the other hand I got to know that we have to live a professional life in this professional world.

Bitter truth is something that one has to face at some point of time in your life.Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest.

Project Euler 5

Problem: What is the smallest number divisible by each of the numbers 1 to 20?

Solution: [Spoiler Ahead]

I just checked for numbers that are divisible by all numbers between 11 and 20(inclusive), this algo is not much efficient but works well.

Toggle Code

Project Euler 4

Problem: Find the largest palindrome made from the product of two 3-digit numbers.

Solution: [Spoiler Ahead]

The initial algorithm to the problem is : Check all products of two 3-digit number and store the required number.

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