# Kotlin Program to Find LCM Using Prime Factors

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.