Kotlin Program to Find GCD of Number 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.

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.

Support Us

If you like 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.
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