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

Leave a Comment / By /
  • 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

You may also like:

GCD of two numbers Euclidean algorithm in java (iterative/ recursive)

Program to check given input number is even or odd in java (example)

Swap two numbers without using third or temporary variable in java

Check given number is palindrome using java (non-recursive/example)

Convert decimal number to binary – (java api, iterative & recursive)

Program to convert binary number to decimal (java api, iterative & recursive)

Find number of consecutive 1’s in a binary number in java (example)