- LCM (Least common multiple) of two integers is the least positive integer that is divisible by both a and b.
- e.g lcm(10,15) = 30 or lcm(12,18) = 36.
- LCM is also referred as lowest common multiple or smallest common multiple.
- LCM can be calculated by calculating the GCD (greatest common divisor) of two positive integer.
Example: Least common multiple of two numbers
- Find LCM of 10 & 15 using GCD.
- Find GCD of two numbers 10 & 15 using recursive algorithm (refer code section).
- Calculate LCM of two numbers
- LCM (x,y) = x * y / gcd (x,y)
- e.g. gcd (10 , 15) = 5
- LCM (10 , 15) = (10 * 15) / 5 = 30
- LCM (10 , 15) = 30.
Program to find LCM of two natural numbers
package org.learn;
import java.util.Scanner;
public class LCMOfNumbers {
public static void main(String[] args) {
try(Scanner scanner = new Scanner(System.in)) {
System.out.printf("1. Enter first number : ");
int a = scanner.nextInt();
System.out.printf("2. Enter second number : ");
int b = scanner.nextInt();
int lcm = lcm (a,b);
System.out.printf("3. lcm(%d,%d) = %d ", a , b, lcm);
}
}
private static int lcm(int a, int b) {
return (a * b) / gcd(a,b);
}
private static int gcd(int a, int b) {
int temp = 0;
while (b != 0) {
temp = b;
b = a %b;
a = temp;
}
return a;
}
}
Program output to find LCM of two natural numbers:
1. Enter first number : 12
2. Enter second number : 18
3. lcm(12,18) = 36
1. Enter first number : 10
2. Enter second number : 15
3. lcm(10,15) = 30