Tag Archives: lcm

Computing the lowest common multiple (LCM) of a given set of postive integers in java

Lowest common multiple (LCM) of a given set of integers is the smallest integer that is divisible by each of them. In this post I will discuss a method to compute a method to computing the lowest common multiple (LCM) of a given set of positive integers using the Java programming language.

Students are usually tempted to use the division method taught in lower classes to calculate the lowest common multiple because that’s the method they are familiar with, however, the division method is geared towards manual use and is not a preferred choice for computer implementation. Lowest common multiple (LCM) of a given set of number can be easily calculated if store the required numbers in an integer array and then find the lowest integer divisible by all the numbers. This can be accomplishing by starting the loop from 1 and increasing the control variable by one till we get an integer which is divisible by all the integers. The program incorporating the above logic would be as follows:

class LCM{
    public static int getLCM1(int ... a){
        int lcm=0;
        boolean found;
        for(int i=1; ; i++){
            found=true;
            for(int x=0; x<a.length;x++){
                if(i%a[x]!=0){
                    found=false;
                    break;
                }
            }
            if(found){
                lcm=i;
                break;
            }
        }
        return lcm;
    }
    public static void main(String[] args){
        int a[]={2,5,7};
        System.out.println(getLCM1(a));
    }
}

The above method will give correct answer but is not very efficient. The efficiency could be increased if we use the following improvisations:

  1. Lowest common multiple (LCM) of a given set of positive integers cannot be lower than the highest number in the set.
  2. If the highest number in the set is not the Lowest common multiple (LCM) then instead of increasing it by one we can increase it in multiples of the lowest number, this way number of checks will be drastically reduced.

The following program implements the above logic inside the getLCM2( ) functions:

class LCM{
    public static int getLCM1(int ... a){
        int lcm=0;
        boolean found;
        for(int i=1; ; i++){
            found=true;
            for(int x=0; x<a.length;x++){
                if(i%a[x]!=0){
                    found=false;
                    break;
                }
            }
            if(found){
                lcm=i;
                break;
            }
        }
        return lcm;
    }
    public static int getLCM2(int ... a){
        int lcm, min;
        boolean found;
        max=a[0];
        for(int i=0; i<a.length; i++){
            if(a[i]<min) min=a[i];
        }
        for(int i=max; ; i+=min){
            found=true;
            for(int x=0; x<a.length;x++){
                if(i%a[x]!=0){
                    found=false;
                    break;
                }
            }
            if(found){
                lcm=i;
                break;
            }
        }
        return lcm;
    }
    public static void main(String[] args){
        int a[]={2,5,7};
        System.out.println(getLCM1(a));
        System.out.println(getLCM2(a));
    }
}

As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.