Find LCM of two numbers using GCD in java (example)

  • 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

  1. Find LCM of 10 & 15 using GCD.
  2. Find GCD of two numbers 10 & 15 using recursive algorithm (refer code section).
    • gcd (10 , 15) = 5
  3.  Calculate LCM of two numbers
    • LCM (x,y) = x * y / gcd (x,y)
      1. e.g. gcd (10 , 15) = 5
      2. LCM (10 , 15) = (10 * 15) / 5 = 30
      3. 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 
Scroll to Top