Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Euclidean algorithm — Greatest Common Divisor(GCD)

The great­est com­mon divi­sor (GCD) of two or more inte­gers, when at least one of them is not zero, is the largest pos­i­tive inte­ger that divides the num­bers with­out a remain­der. For exam­ple, the GCD of 10 and 15 is 5. (Source — Wiki — http://en.wikipedia.org/wiki/Greatest_common_divisor).

Euclid­ean Algo­rithm : The great­est com­mon divi­sor of two num­bers remains the same if the larger num­ber is replaced by its dif­fer­ence with the smaller num­ber. If we keep repeat this process until one of the num­ber becomes 0, then other num­ber will be the GCD. We can solve this recursively.

Exam­ple:

GCD of 282 and 156 will be the same as 156 and (282-156)=126.
GCD of 156 and 126 will be the same as 126 and (156-126) = 30
GCD of 126 and 30 will be the same as 18 and (126-30) = 96
GCD of 96 and 30 will be the same as 30 and (96-30) = 66
GCD of 66 and 30 will be the same as 30 and (66-30) = 36
GCD of 36 and 30 will be the same as 30 and (36-30) = 6
GCD of 6 and 30 will be the same as 6 and (30-6) = 24
GCD of 24 and 6 will be the same as 6 and (24-6) = 18
GCD of 6 and 18 will be the same as 6 and (18-6) = 12
GCD of 12 and 6 will be the same as 6 and (12-6) = 6
GCD of 6 and 6 will be the same as 6 and (6-6) = 0

one number becomes 0, other number 6 will be the GCD.

 

Com­plete Code:


Out­put:

 6

You may also like...