###### Greetings!

We have recently published 100+ articles on android tutorials with kotlin and java. If you need, you may visit Android Tutorial for beginners page. You can also check Kotlin Tutorial for beginners. Also, if you are interested in content writing, you can mail us at**tutorialwing@gmail.com**.

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.

## Support Us

**Tutorialwing**and would like to contribute, you can email an article on any educational topic at tutorialwing@gmail.com. We would love to publish your article. See your article on Tutorialwing and

**help others with your knowledge**. Follow Facebook, LinkedIn, Google+, Twitter, Youtube for latest updates.