In this post, we will go through kotlin program to find LCM of two numbers using GCD with euclidean Algorithm.

What is LCM?

LCM (Least Common Multiple) of two numbers is smallest number that is divisible by both.

For Example,

LCM of 13 and 21 is 273
Explanation:

273 / 13 = 21
273 / 21 = 13

We can find LCM using below ways –

1. Simple Way
2. Using Prime Factors
3. Using GCD

3. Program to Find LCM of Two Numbers (Using GCD)

GCD stands for Greatest Common Divisor. It means for any two numbers a and b, largest number that can divide a and b both.

We use below concepts to find lcm using gcd.

For any numbers a and b,

LCM * GCD = Product of Two Numbers = a * b

So,

LCM = (a * b) / GCD

Sourcecode –

import java.util.*

fun main() {

    val read = Scanner(System.`in`)

    println("Enter a:")
    val a = read.nextInt()

    println("Enter b:")
    val b = read.nextInt()

    // Find GCD
    val gcd = findGCD(a, b)

    // Find LCM using GCD.
    val lcm = (a * b) / gcd

    println("LCM of $a and $b: $lcm")
}

private fun findGCD(a: Int, b: Int): Int {

    if(a == 0) return b

    return findGCD(b % a, a)
}

When you run the program, output will be –

Enter a:
90
Enter b:
120
LCM of 90 and 120: 360

Explanation:

Here, we have used euclidean algorithm to find GCD (greatest common divisor) of two numbers.

Thus, we went through Kotlin Program to find LCM using GCD of two numbers. We have also learnt how to use euclidean algorithm to find lcm (Least Common Multiple)