Java Program to Find LCM and GCD of Two Numbers

  • Write a program in java to find gcd and lcm of two given numbers using loop and recursion.

Given two integers, we have to find the lcm and gcd of two numbers. Before jumping into java program, here is the brief introduction of lcm and gcd od two numbers.

  • The Least Common Multiple (LCM) of two integers a and b, usually denoted by LCM (a, b), is the smallest positive integer that is divisible by both a and b.
  • The Highest Common Factor (HCF) of two or more integers, is the largest positive integer that divides the numbers without a remainder. HCF is also known as greatest common divisor(GCD) or greatest common factor(GCF).

If we know LCM or HCF of two numbers, then we can find the other one using below equation.

LCM(A, B) X HCF(A, B) = A*B

Java Program to calculate lcm and hcf

In this program, we first take two numbers as input from user and store them in variable "a" and "b". Then using a while loop, we calculate the gcd of a and b and store it in variable gcd. To calculate lcm we use above mentioned equation, lcm = (a*b) / gcd.

package com.tcc.java.programs;

import java.util.Scanner;

/**
 * Java Program to print LCM and GCD of two numbers
 */
public class PrintLcmHcf {

    public static void main(String[] args) {
        int a, b, t, aTemp, bTemp, lcm, gcd;
        Scanner scanner;
        scanner = new Scanner(System.in);
        // Take two numbers from user
        System.out.println("Enter Two Number");
        a = scanner.nextInt();
        b = scanner.nextInt();

        aTemp = a;
        bTemp = b;

        while (bTemp != 0) {
            t = bTemp;
            bTemp = aTemp % bTemp;
            aTemp = t;
        }

        gcd = aTemp;

        /*
         * GCD(a, b) * LCM(a, b) = a*b
         */
        lcm = (a * b) / gcd;
        System.out.println("LCM = " + lcm);
        System.out.println("GCD = " + gcd);
    }
}
Output
Enter Two Number
6 14
LCM = 42
GCD = 2

Java program to calculate lcm and gcd using recursion

This java program is similar to above program except that here we are using a user defined recursive function "getGcd" which takes two integers are input parameters and return the gcd of two numbers.

package com.tcc.java.programs;

import java.util.Scanner;

/**
 * Java Program to print LCM and GCD of two numbers using recursion
 */
public class PrintLcmHcfFunction {

    public static void main(String[] args) {
        int a, b, t, aTemp, bTemp, lcm, gcd;
        Scanner scanner;
        scanner = new Scanner(System.in);
        // Take two numbers from user
        System.out.println("Enter Two Number");
        a = scanner.nextInt();
        b = scanner.nextInt();

        gcd = getGcd(a, b);
        /*
         * GCD(a, b) * LCM(a, b) = a*b
         */
        lcm = (a * b) / gcd;
        System.out.println("LCM = " + lcm);
        System.out.println("GCD = " + gcd);
    }

    /**
     * Returns LCM and GCD of a and b
     */
    public static int getGcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return getGcd(b, a % b);
        }
    }
}
Output
Enter Two Number
4 22
LCM = 44
GCD = 2