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

Recommended Posts
Java Program to Calculate Arithmetic Mean of N Numbers
Java Program to Check a Number is Prime Number or Not
Java Program to Find All Factors of a Number
Java Program to Find Factorial of a Number using For Loop
Java Program to Find Sum of Digits of a Number
Java Program to Print Prime Numbers between 1 to 100
Java Program to Convert Decimal to Binary Numbers
Java Program to Check If a Year is Leap Year or Not
Java Program to Make a Simple Calculator using Switch Statement
Java Program for Matrix Multiplication
Java Program to Search an Element in an Array using Linear Search
All Java Programs