# How to find the number that's evenly divisible by a set of numbers from 1 to n?

1. Aug 17, 2011

### newb

How can you go about finding the smallest number (x) that is evenly divisible by a set of numbers from 1 to n?

For example:

If n = 3, x=6
n = 4, x=12
n=5, x=60
n=6, x=60

This is easy to do when n is a small number, however how would one go about finding the answer if n=20 for example?

I have written a program that tries to brute force the answer, but I'm almost certain there's a much more elegant way to do it. Any advice?

2. Aug 17, 2011

### newb

Here's the program I wrote by the way, incase anyone is interested:
Code (Text):

class Problem5 {
static int[] theArray;
static int multiplyer = 11 ;
static boolean test= false;
static int current;

//Makes array
void maker (int number){
for(int i=number; i>0; i--){
theArray[i-1]=i;

}
}

public static void main (String[] args){

Problem5 instance1 = new Problem5();
theArray = new int[multiplyer];
instance1.maker(multiplyer);
current = theArray[theArray.length-1];
System.out.println (current);

while (test == false){
for(int i = theArray.length; i>0; i--){
if (current % theArray[i-1]>0){
current = current + theArray[multiplyer -1];
i=0;
test = false;
} else{
System.out.println(current+" is divisible by "+ theArray[i-1]);
test = true;
}
}
}

}

}

Last edited by a moderator: Aug 17, 2011
3. Aug 17, 2011

### sir_manning

Phrased another way, your problem is to find the lowest common multiple (LCM) of a set of numbers from 1,...,n . Luckily, there is an easy formula to get the LCM for two numbers a and b from the greatest common divisor (GCD): LCM(a,b) = |a*b|/GCD(a,b) . I say luckily because finding the GCD is easy - just use the Euclidean algorithm. There's probably a snazzy way to deal with this for more than two numbers but you could adopt it by finding LCM(a,b), then LCM(LCM(a,b),c), etc. Check out http://en.wikipedia.org/wiki/Least_common_multiple

If you stick with a brute force approach, remember that apart from {1}, each set contains 2. Think about what this means for the LCM...