Problem 6: Sum of squares or Square of sum !!!!

Q. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.


Sol: 
I think problem is also one of the easiest problems here. 
The problem can be easily solved through basic knowledge of Arithmetic-Geometric Progression....


We know that sum of squares of numbers from 1 to n is n(n+1)(2n+1)/6 and sum of the numbers from 1 to n is n(n+1)/2.
So, the result can be formulated into an expression


Difference= (n(n+1)/2) ^ 2  - n(n+1)(2n+1)/6 = n(n+1)( 3(n^2) - n -2 ) / 12


Now all that remains is calculation.......  :D


Please post your comments...
Suggestion for better algorithms are always welcome.....

Problem 5:Least evenly divisible number

Q. 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.What is the smallest number that is evenly divisible by all of the numbers from 1 to 20 ?

Sol:

It can be easily seen that the question is asking the LCM of the numbers.The problem can be solved without even resorting to algorithms.Just compute the prime factorization of numbers and multiply the highest power of each prime.

20 = 2^2 * 5
19 = 19
18 = 2 * 3^2
17 = 17
16 = 2^4
15 = 3 * 5
14 = 2 * 7
13 = 13
11 = 11 

Since all the lesser numbers have been included, they can be safely ignored..

And

lcm= 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

Now, the problem seems so simple, but what if we were to calculate the result for natural numbers from 1 to an arbitrary number(say ' n ').

It can be observed that 

LCM(a,b,c,d)=LCM(b,c,LCM(a,d))

To implement it, we can run a loop from 2 to n-1 and at each step find the lcm of loop variable and the previous stage lcm.The lcm can be easily found by applying euclid's algorithm of finding GCD as

 LCM(a,b)=(a*b)/GCD(a,b).

Now the coding part:

int main()

{

scanf("%d",&lastnumber);

long n=20;

 for(i=2;i < 20; i++)

 {

                  n=(n*i)/gcd(n,i);

 }

 printf(" %ld \n", n);

return 0;

}

The euclid's algo can be implemented as:

int gcd(int a,int b)

{

    if(a == 0)

       return b;

    while(b != 0)

        if (a > b)

           a = a - b;

        else

           b = b - a;

    return a;

}

Thats all it is to the problem :D

Please post your comments and doubts...
Suggestion for better algorithms are always welcome.....