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[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:
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.