Euclidean Algorithm: An effective way to find greatest common divisor (GCD)

In this article, we are going to learn what is Euclidean algorithm? How to calculate greatest common divisor of two numbers using Euclidean algorithm and program in Kotlin.
Submitted by Aman Gautam, on December 20, 2017

Euclidean algorithm is an efficient algorithm to calculate greatest common divisor of two number. A simple way is to find factors of both the numberand then multiply common factors. But this is little bit tricky programmatically. So Euclidean algorithm is the optimal solution for finding GCD.

Example: GCD(93,219)

219 = 93 x 2 + 33
 93 = 33 x 2 + 27
 33 = 27 x 1 + 6
 27 = 6 x 4 + 3
  6 = 3 x 2 + 0

Since the non-zero remainder is 3, so 3 is the GCD of 93 and 219.

Algorithm

1) Iterative Algorithm

    GCD(a,b)
    1.	while (b != 0) 
    2.	temp = b
    3.	    b = a % b;
    4.	    a = t;
    5.	return a

2) Recursive Algorithm

    GCD(a,b)
    1.	if (b == 0)
    2.	    return a
    3.	else
    4.	    return gcd(b, a % b)

Time complexity: O(Log min(a, b))

Program to implement Euclidean Algorithm in Kotlin

fun gcd_1(a:Int, b:Int) :Int {
    var a=a
    var b=b
    while (b != 0) {
        var t = b;
        b = a % b;
        a = t;
    }
    return a
}
fun gcd_2(a:Int, b:Int) :Int {
    if (b == 0)
    return a
    else
    return gcd_2(b, a % b)
}

fun main(args: Array<String>) {
    println("Enter two number ")
    var a = readLine()!!.toInt()
    var b = readLine()!!.toInt()

    println("Using iterative function GCD = ${gcd_1(a, b)}")
    println("using recursive function GCD = ${gcd_2(a, b)}")
}

Output

Enter two number 
93
219
Using iterative function GCD = 3
using recursive function GCD = 3

Comments and Discussions!

Load comments ↻