In this post, we will go through kotlin program to find LCM of two numbers using prime factors.

What is LCM?

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

For Example,

LCM of 90 and 120 is 360

Explanation:

360 / 90 = 4
360 / 120 = 3

We can find LCM using below ways –

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

In this post, we learn to find LCM using prime factors.

1. Program to Find LCM of Two Numbers (Using Prime Factors)

We can find lcm (least common multiple) of two numbers using Prime Factorisation.

Pseudo Algorithm

• Find prime factors of a and b in array aFactors and bFactors.
• Calculate union of both prime factors
• Multiply that factors to get lcm

import java.util.*
import kotlin.collections.HashMap
import kotlin.math.sqrt

fun main() {

    val scanner = Scanner(System.`in`)

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

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

    val aFactors = primeFactors(a)
    val bFactors = primeFactors(b)


    var lcm = if (aFactors.size > 0 && bFactors.size > 0) 1 else 0

    // Compare factors of a and b.
    for (mapEntry in aFactors) {
        val aCount = mapEntry.value
        val bCount = bFactors[mapEntry.key]

        if (bCount != null) { // If factors of a are present in b.

            // Find maximum count of factors in a and b.
            val maxCount = if (bCount > aCount) bCount else aCount

            // Multiply key up-to maxCount times with lcm.
            for (index in 1..maxCount) lcm *= mapEntry.key
        } else { // If factors of a are not present in b.
            for (index in 1..aCount) lcm *= mapEntry.key
        }
    }

    // If factors of b are not present in a.
    for (mapEntry in bFactors) {
        val bCount = mapEntry.value
        val aCount = aFactors[mapEntry.key]
        if (aCount == null) {
            for (index in 1..bCount) lcm *= mapEntry.key
        }
    }

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

private fun primeFactors(number: Int): HashMap<Int, Int> {

    // Hash map that contains all the prime factors of given number.
    val map: HashMap<Int, Int> = HashMap()


    var n = number

    if (n <= 0) {
        return map
    }

    // At first check for divisibility by 2.
    // Add it in arr till it is divisible
    var count = 1
    while ((n % 2) == 0) {
        map[2] = count
        count++
        n /= 2
    }

    val squareRoot = sqrt(n.toDouble()).toInt()

    // Run loop from 3 to square root of n.
    // Check for divisibility by i.
    // Add i in map till it is divisible by i.
    for (i in 3..squareRoot step 2) {
        count = 1
        while (n % i == 0) {
            map[i] = count
            count++
            n /= i
        }
    }

    // If n is a prime number greater than 2.
    if (n > 2) {
        count = 1
        map[n] = count
    }

    return map
}

When you run the program, output will be –

Enter a:
120
Enter b:
200
LCM of 120 and 200: 600

Explanation:.

Here, we find factors of a and store it in aFactors.
Then, we find factors of b and store it in bFactors.

Then, we find union of both array aFactors and bFactors
There are three scenarios –

1. Factors of a are present in b.: Find maximum count (i.e. maxCount) of occurrence. Then, run a loop and multiply that factor up-to maxCount times.
2. Factors of a are not present in b.: Then, run a loop and multiply that factor up-to aCount times.
3. Factors of b are not present in a.: Then, run a loop and multiply that factor up-to bCount times.

Finally, we get lcm of a and b.

Thus, we went through Kotlin Program to find LCM using prime Factors of two numbers.