# Kotlin Program to Find GCD of Number Using Prime Factors

Write a Kotlin program to find GCD of a given number n using prime factors.

For example,

Given n = 45
Output

```3 3 5
```

Given n = 30

```2 3 5
```

Common Prime Factors : 3, 5

GCD = 3 * 5 = 15

## 1. Program to find GCD of Number (Using Prime Factors)

```import java.util.*
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 gcd = if (aFactors.size > 0 && bFactors.size > 0) 1 else 0

// Compare factors of a and b. Find the common factors
// and multiply it with gcd to compute final hcf.
for (mapEntry in aFactors) {
val aCount = mapEntry.value
val bCount = bFactors[mapEntry.key]
if (bCount != null) {

// Find how many times each factor (i.e. key) is common in a and b map.
val commonCount = if (bCount > aCount) aCount else bCount

// Multiply key up-to commonCount times with gcd.
for (index in 1..commonCount) gcd *= mapEntry.key
}
}

println("GCD of \$a and \$b: \$gcd")
}

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<Int, Int>()

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:
30
Enter b:
45
GCD of 30 and 45: 15
```
###### Explanation:

primFactors returns a hashMap that contains all prime factors of given number.

For example,

Let’s assume we have entered a = 30, and b = 45.

For number n = 30,
Returned hashMap will be –

```{
2: 1,
3: 1,
5: 1
}
```

This map will be stored in aFactors.

For number n = 45,
Returned hashMap will be –

```{
3: 1,
3: 1,
5: 1
}
```

This map will be stored in bFactors.

Now, we run a for loop on aFactors to find common factors between a and b.
We multiply each time we find a common factor with gcd to calculate final gcd.

Thus, we went through Kotlin program to find GCD of a given number n using prime factors.