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