# Euclides Algorithm (GCD)

Program the Greatest Common Divisor/Denominator

In mathematics, the greatest common divisor / denominator (GCD) or greatest common factor (GCF) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 136 and 600 is 8.

Maybe, the first idea that comes to mind to find the GCD is to write a loop that checks every number that is less than the two numbers. The **Euclidean Algorithm** however is a better way of finding the GCD.

The

Euclidean Algorithm: Given two numbers, repeatedly replace the larger number with the greater number mod the lesser number. Keep repeating the step until one of the two numbers reaches zero, the other number will then be the greatest common denominator (or greatest common divisor), the GCD.

`GCD(A,B) → B = quotient * A + remainder, where A<=B `

Let’s use the Euclidean algorithm to find the greatest common divisor of *A= 136 *and *B= 600*. To begin, multiples of 136 are subtracted from 600 until the remainder is less than 136. Four such multiples can be subtracted (*q*0 = 4), leaving a remainder of 56. **NOTE: ‘q’ is our quotient → ‘q0’ is our first quotient**:

600 = 4 × 136 + 56.

Then multiples of 56 are subtracted from 136 until the remainder is less than 56. Two multiples can be subtracted (*q*1 = 2), leaving a remainder of 24:

136 = 2× 56 + 24.

Then multiples of 24 are subtracted from 56 until the remainder is less than 24. Two multiples can be subtracted (*q*2 = 2), leaving a remainder of 8:

56 = 2× 24 + 8.

Then multiples of 8 are subtracted from 24 until the remainder is less than 8. Three multiples can be subtracted (*q*2 = 3), leaving no remainder:

24 = 3× 8 + 0.

Since the last remainder is zero, the algorithm ends with 8 as the greatest common divisor of 600 and 136. This agrees with the function GCD(136, 600) .

**Note:** In the above steps for GCD(136,600) that 136 is less than 600, if we had GCD(600,136) then we will need to swap the two numbers, since 600 > 136.

# Get The Recursive C-Program Below:

# Get The Iterative (for-loop) C-Program Below:

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

# Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

**YouTube Channel:***randerson112358:*https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

*compsci112358:*

https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

**Website:**

http://everythingcomputerscience.com/

**Video Tutorials on Recurrence Relation:**

https://www.udemy.com/recurrence-relation-made-easy/

**Video Tutorial on Algorithm Analysis:**

https://www.udemy.com/algorithm-analysis/

**Twitter:**

https://twitter.com/CsEverything