CodeCrucks

CodeCrucks

Program to Find LCM of Two Numbers using Recursion

Program to Find LCM of Two Numbers using Recursion

by · Published · Updated

  • Write a program to Find LCM of Two Numbers using Recursion in C
  • Write a program to Find LCM of Two Numbers using Recursion in C++
  • Write a program to Find LCM of Two Numbers using Recursion in Python
  • Write a program to Find LCM of Two Numbers using Recursion in PHP
  • Write a program to Find LCM of Two Numbers using Recursion in Java
  • Write a program to Find LCM of Two Numbers using Recursion in Java Script
  • Write a program to Find LCM of Two Numbers using Recursion in C#

Explanation:

The smallest positive integer that may be divided by two numbers is called the LCM (Least Common Multiple). The LCM can be effectively calculated using the relationship between GCD (Greatest Common Divisor) and LCM:

LCM(a, b) = |a . b| / GCD(a, b)

The first common multiple can be found by iteratively checking multiples of the larger integer if we wish to compute the LCM directly using recursion.

Algorithm

  1. Define a function to calculate GCD recursively:
    • Base case: If b == 0, return a.
    • Recursive case: Return GCD(b, a % b).
  2. Calculate LCM using the formula: LCM(a,b) = ∣a⋅b∣ / GCD(a,b)

Program to Find LCM of Two Numbers using Recursion

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int a, b;
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);

    printf("LCM of %d and %d is %d\n", a, b, lcm(a, b));
    return 0;
}


#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int a, b;
    cout << "Enter two numbers: ";
    cin >> a >> b;

    cout << "LCM of " << a << " and " << b << " is " << lcm(a, b) << endl;
    return 0;
}


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return (a * b) // gcd(a, b)

a = int(input("Enter the first number: "))
b = int(input("Enter the second number: "))

print(f"LCM of {a} and {b} is {lcm(a, b)}")


<?php
function gcd($a, $b) {
    if ($b == 0)
        return $a;
    return gcd($b, $a % $b);
}

function lcm($a, $b) {
    return ($a * $b) / gcd($a, $b);
}

echo "Enter the first number: ";
$a = intval(trim(fgets(STDIN)));
echo "Enter the second number: ";
$b = intval(trim(fgets(STDIN)));

echo "LCM of $a and $b is " . lcm($a, $b) . "\n";
?>


import java.util.Scanner;

public class Main {
    public static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the first number: ");
        int a = scanner.nextInt();
        System.out.print("Enter the second number: ");
        int b = scanner.nextInt();

        System.out.println("LCM of " + a + " and " + b + " is " + lcm(a, b));
    }
}


function gcd(a, b) {
    if (b === 0)
        return a;
    return gcd(b, a % b);
}

function lcm(a, b) {
    return (a * b) / gcd(a, b);
}

const a = parseInt(prompt("Enter the first number:"));
const b = parseInt(prompt("Enter the second number:"));

console.log(`LCM of ${a} and ${b} is ${lcm(a, b)}`);


using System;

class Program {
    static int GCD(int a, int b) {
        if (b == 0)
            return a;
        return GCD(b, a % b);
    }

    static int LCM(int a, int b) {
        return (a * b) / GCD(a, b);
    }

    static void Main() {
        Console.Write("Enter the first number: ");
        int a = int.Parse(Console.ReadLine());
        Console.Write("Enter the second number: ");
        int b = int.Parse(Console.ReadLine());

        Console.WriteLine($"LCM of {a} and {b} is {LCM(a, b)}");
    }
}

List of All Programs