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 –

- Find Common Prime Factors. : Find Common Prime Factors of both numbers and multiply them to get HCF
- Use Euclidean algorithm : We will use euclidean algorithm to find GCD (or HCF)
- 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

aandb,

- If we subtract smaller from larger number, their gcd does not change. i.e.
gcd(a, b) = gcd(a, b – a)provideda < 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.