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 –

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 –

**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.**Factors of a are not present in b.**: Then, run a loop and multiply that factor up-to aCount times.**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.