Pages

February 24, 2011

Project Euler 5



ProblemWhat 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






ProblemFind 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.




February 23, 2011

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