LCM of Two Numbers using Recursion in Java

October 12, 2022

LCM of Two Numbers using Recursion in Java

Here, in this page we will discuss the program to find the LCM of Two numbers using Recursion in Java Programming Language. We are given with two integers and need to find the LCM of the given numbers.  The LCM of two integers num1 and num2 is the smallest positive integer that is perfectly divisible by both num1 and num2(without a remainder). 

Example :

  • Input : num1 = 3 num2 = 21
  • Output : LCM of 3 and 21 is 21.
LCM of Two Numbers using Recursion in C++

Different Methods Discussed in this page :

We have discussed the following methods using recursion to find the HCF of given two numbers and then can find the LCM using that HCF.

  • Method 1 :Recursive Euclidean Algorithm: Repeated Subtraction to calculate the HCF
  • Method 2: Modulo Recursive Euclidean Algorithm: Repeated Subtraction to calculate the HCF

 

Method 1 :

This method is based on  Euclidean Algorithm.

  • Create a variable say HCF to hold the value return by getHCF(int num1, num2).
  • Then calculate the LCM = (num1 *num2)/HCF

Code to find LCM of a Number using Recursion

Run 
public
class Main {
    // Recursive method to return gcd of a and b
    static int gcd(int a, int b) {
        if (a == 0) return b;
        return gcd(b % a, a);
    }
    // method to return LCM of two numbers
    static int lcm(int a, int b) {
        return (a / gcd(a, b)) * b;
    }
    // Driver method
    public
    static void main(String[] args) {
        int a = 15, b = 20;
        System.out.println("LCM of " + a + " and " + b + " is " + lcm(a, b));
    }
}
LCM of 15 and 20 is 60

Method 2

This method uses recursion.

In Addition, we are using modulo operation to reduce the number of subtractions required and improve the time complexity

For this method, you need to know how to calculate HCF, check this post here

We use repeated Modulo Recursive subtraction (Euclidean Algorithm) to calculate the HCF.

Run 
public
class Main {
    public
    static void main(String[] args) {
        int num1 = 144, num2 = 32;
        int hcf = getHCF(num1, num2);
        System.out.println("The HCF: " + hcf);
        // LCM formula
        int lcm = (num1 * num2) / hcf;
        System.out.println("The LCM: " + lcm);
    }
    // This method improves complexity of repeated substraction
    // By efficient use of modulo operator in euclidean algorithm
    static int getHCF(int a, int b) {
        return b == 0 ? a : getHCF(b, a % b);
    }
}

Output

The HCF: 16
The LCM: 288
 
 

Smallest element in an array

Prime Number

Largest element in an array

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime