In this post, we will go through Kotlin program to find GCD or HCF of two numbers.

What is GCD or HCF?

GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest number that divides both of them.

For Example,

GCD of 30 and 20 is 10
Explanation:

Prime Factors of 30 = 1 X 2 X 3 X 5
Prime Factors of 20 = 1 X 2 X 2 X 5

Common Prime Factors between 30 and 20 are 1, 2 and 5.
So,
GCD of 30 and 20 is multiplication of Common Prime Factors of 30 and 20.
i.e.
GCD of 30 and 20 = 1 X 2 X 5 = 10

There are many ways to write program to find GCD of two numbers. Some are –

1. Find Common Prime Factors. : Find Common Prime Factors of both numbers and multiply them to get HCF
2. Use Euclidean algorithm : We will use euclidean algorithm to find GCD (or HCF)
3. Use Euclidean algorithm (Using modulo operator) : A better implementation using euclidean algorithm using modulo operator

In this post, we will use basic euclidean algorithm to find GCD or HCF.

2. Program to find GCD (or HCF) of Two Numbers Using Euclidean Algorithm

Basic Euclidean Algorithm

For integer a and b,

• If we subtract smaller from larger number, their gcd does not change. i.e. gcd(a, b) = gcd(a, b – a) provided a < b. So, if we repeatedly subtract smaller from larger number, finally, we will get gcd of two number.
• We can also divide larger number by smaller. In this case, algorithm will stop when we get 0 as remainder.

Sourcecode –

import java.util.*

fun main() {

    val read = Scanner(System.`in`)

    println("Enter a:")
    val a = read.nextInt()

    println("Enter b:")
    val b = read.nextInt()

    val gcd = findGCD(a, b)

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

private fun findGCD(a: Int, b: Int): Int {

    if(a == 0) return b

    return findGCD(b % a, a)
}

When you run the program, output will be

Enter a:
20
Enter b:
30
GCD of 20 and 30: 10

Here, we have created an object of Scanner. Scanner takes an argument which says where to take input from.
System.`in` means take input from standard input – Keyboard.

read.nextIn() means read anything entered by user before space or line break from standard input – Keyboard.
Input read by scanner is then stored in variable number

Let Assume a = 20, b = 30

So, first call of findGCD() method
a = 20, b = 30
a != 0. So, findGCD(30 % 20, 20) = findGCD(10, 20) will be called

2nd call of findGCD() method,
Now, a = 10, b = 20
a != 0. So, findGCD(20 % 10, 10) = findGCD(0, 10) will be called

3rd call of findGCD() method,
Now, a = 0, b = 10
a == 0. So, b (=10) will be returned.

Finally, 10 will be returned that is GCD of 20 and 30.

Thus, we went through Kotlin program to find GCD or HCF of two numbers.