Project Euler Solution 5

Problem Statement#

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

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution#

Let us see, what is the smallest number divisible by each of the numbers 1 to 5?

The divisors are 1, 2, 3, 4 and 5.

Since our answer should be divisible by 5, I considered only the numbers that are multiples of 5.

Multiples of 5	5	10	15	20	25	30	35	40	45	50	55	60	65
2		Yes		Yes		Yes		Yes		Yes		Yes
3			Yes			Yes			Yes			Yes
4				Yes				Yes				Yes

The first row shows the numbers that are multiples of 5.(Note: In program I have considered multiples of MAX which is 20).

Now we are checking whether these numbers are divisible by the numbers from 2 to 4 (in program 2 to < MAX).

Stop checking once we find a number that is a multiple of numbers from 2 to 4.(In the program I have done this as if(j==MAX-1))

In this example 60 is the smallest number divisible by each of the numbers from 1 to 5.

Implementation#

#include <iostream>
using namespace std;
int MAX = 20;
int main(){    int i, j;    i = MAX;    while (i != 0)    {        for (j = 2; j < MAX; j++)        {            if ((i % j) != 0) break;            if (j == (MAX - 1))            {                cout << i;                return 0;            }        }        i += MAX;    }    return 0;}

Sample Output#

Sample Output