# Smallest number that is evenly divisible by all of the numbers from 1 to 20?

### Question

I did this problem [Project Euler problem 5], but very bad manner of programming, see the code in c++,

``````#include<iostream>
using namespace std;
// to find lowest divisble number till 20

int main()
{
int num = 20, flag = 0;

while(flag == 0)
{
if ((num%2) == 0 && (num%3) == 0 && (num%4) == 0    && (num%5) == 0 && (num%6) == 0
&& (num%7) == 0 && (num%8) == 0 && (num%9) == 0 && (num%10) == 0 && (num%11) == 0 && (num%12) ==0
&& (num%13) == 0 && (num%14) == 0 && (num%15) == 0 && (num%16) == 0 && (num%17) == 0 && (num%18)==0
&& (num%19) == 0    && (num%20) == 0)

{
flag =  1;
cout<< " lowest divisible number upto 20 is  "<< num<<endl;
}

num++;
}

}
``````

i was solving this in c++ and stuck in a loop, how would one solve this step......

• consider num = 20 and divide it by numbers from 1 to 20
• check whether all remainders are zero,
• if yes, quit and show output num
• or else num++

i din't know how to use control structures, so did this step

``````if ((num%2) == 0 && (num%3) == 0 && (num%4) == 0    && (num%5) == 0 && (num%6) == 0
&& (num%7) == 0 && (num%8) == 0 && (num%9) == 0 && (num%10) == 0 && (num%11) == 0 && (num%12) ==0
&& (num%13) == 0 && (num%14) == 0 && (num%15) == 0 && (num%16) == 0 && (num%17) == 0 && (num%18)==0
&& (num%19) == 0    && (num%20) == 0) `
``````

how to code this in proper manner?

``````abhilash@abhilash:~\$ ./a.out
lowest divisible number upto 20 is  232792560
``````
1
8
1/22/2015 6:17:25 PM

There is a faster way to answer the problem, using number theory. Other answers contain indications how to do this. This answer is only about a better way to write the `if` condition in your original code.

If you only want to replace the long condition, you can express it more nicely in a for loop:

`````` if ((num%2) == 0 && (num%3) == 0 && (num%4) == 0    && (num%5) == 0 && (num%6) == 0
&& (num%7) == 0 && (num%8) == 0 && (num%9) == 0 && (num%10) == 0 && (num%11) == 0 && (num%12) ==0
&& (num%13) == 0 && (num%14) == 0 && (num%15) == 0 && (num%16) == 0 && (num%17) == 0 && (num%18)==0
&& (num%19) == 0    && (num%20) == 0)
{ ... }
``````

becomes:

``````{
int divisor;
for (divisor=2; divisor<=20; divisor++)
if (num%divisor != 0)
break;
if (divisor != 21)
{ ...}
}
``````

The style is not great but I think this is what you were looking for.

10
1/25/2010 11:08:07 PM

The smallest number that is divisible by two numbers is the LCM of those two numbers. Actually, the smallest number divisible by a set of N numbers x1..xN is the LCM of those numbers. It is easy to compute the LCM of two numbers (see the wikipedia article), and you can extend to N numbers by exploiting the fact that

``````LCM(x0,x1,x2) = LCM(x0,LCM(x1,x2))
``````

Note: Beware of overflows.

Code (in Python):

``````def gcd(a,b):
return gcd(b,a%b) if b else a

def lcm(a,b):
return a/gcd(a,b)*b

print reduce(lcm,range(2,21))
``````