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?

answer for this problem is:

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

Accepted Answer

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

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon