Finding the greatest common divisor using Euclidean algorithm

In this tutorial, I will show how to find the greatest common divisor using Euclidean Algorithm.

The greatest common divisor is a number which is the largest divisor of two or more numbers. It means that two numbers can be divided by GCD without remainder.

For example: The greatest common divisor of 455 and 637 is 91. 91 is the largest number which divides 455 and 637 without remainder.

In order to find GCD you can use Euclidean Algorithm.

This is an example how to find GCD using Euclidean Algorithm.

Step 1. We have 2 numbers: 455 and 637. We take greater number – 637 and divide it by less number 455. Put remainder below of greater number: 637 % 455 = 182

Step 2. Now we have 2 numbers: 455 and 182. Divide 455 by 182 and put remainder below of greater number. 455 % 182 = 91

Step 3. We have 2 numbers: 91 and 182. Divide 182 by 91 and put remainder below of greater number. 182 % 91 = 0. 2 numbers remain: 91 and 0. 91 is the greatest common divisor. The key point is to go until we have one 0. In that case, non zero number is GCD.

I hope you understood the logic how algorithm works. Now let me show Kotlin code for this algorithm:

Leave a comment

Your email address will not be published. Required fields are marked *