# 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 ")

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
```

What's New

Top Interview Coding Problems/Challenges!

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates