# Kotlin Program to Find LCM Using Prime Factors

###### 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 = 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.