Introduction

LCM stands for least common multiple. In simpler words, the LCM of two numbers is the lowest number that can get divided by both numbers with a remainder of zero. For example, the LCM for 15 and 20 is 60, and the LCM for 5 and 7 is 35.

A simple way to think of the solution to the problem is to find all the prime factors of both numbers and then find the union of all the factors contained in both numbers. The LCM of the two numbers will therefore be the product of the elements in the union set.

However, a more efficient way to look at the problem at hand is based on the following formula of calculating the LCM of two numbers, namely ‘a’ and ‘b’.

a * b = LCM (a , b) * GCD (a , b)

LCM (a, b) = (a * b) / GCD (a , b)

Note that the GCD function that has been used here is the function to find the greatest common divisor of two numbers. To find the GCD, the following solution can be implemented:

A simple solution to finding the greatest common divisor of two numbers is to find the prime factors of both numbers. Thereafter, we need to find the intersection of the factors in both sets. The GCD is therefore given by the product of the factors in the intersection set.

Sample Code to find the GCD of two numbers

class Demo
{
static int gcd (int a, int b)
{
if (a == 0)
return b;
if (b == 0)
return a;
if (a == b)
return a;
if (a > b)
return gd (a-b, b);
return gcd (a, b-a);
}
public static void main (String args [])
{
int a = 98, b = 56;
System.out.println (“GCD of the two numbers are” + gcd (a, b));
}
}

OUTPUT

The GCD of the two numbers 98 and 56 is 14.

Euclidean algorithm to find GCD

The Euclidean algorithm can give a more efficient solution to the GCD problem. The idea behind this algorithm is that the GCD of two numbers remains the same even after the smaller number is subtracted from, the bigger number.

Sample Code:

class Test
{
static int gcd (int a, int b)
{
if (b == 0)
return a;
return gd (b, a % b);
}
public static void main (String args [])
{
int a = 98, b = 56;
System.out.println (“GCD of the two numbers is” + gcd (a , b));
}
}

Sample Code to find the LCM of two numbers

Once the GCD of the two numbers in question is found from the above process, the LCM can be easily calculated from the above process.

Sample Code:

class Demo
{
static int gcd (int a, int b)
{
if (a == 0)
return b;
return gcd (b % a, a);
}
static int lcm (int a, int b)
{
return (a / gcd (a, b)) * b;
}
public static void main (String args [])
{
int a = 15, b = 20;
System.out.println (“LCM of ” + a + “ and” + b + “ is” + lcm (a, b) );
}
}

OUTPUT

LCM of 15 and 20 is 60.