Program the Greatest Common Divisor/Denominator

Image for post
Image for post
Image of Euclides

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.

Image for post
Image for post
GCF(136,600) = 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.

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 (q0 = 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 (q1 = 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 (q2 = 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 (q2 = 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:

A Video On Finding The GCD

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store