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

[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?

 

[newb]

Here's the program I wrote by the way, incase anyone is interested:

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;
     }
    }  
   }
     
  }
     
}

 

[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...