Python GCD Program by Successive Division – This Python Programming tutorial will explain the Pthon code to find Greatest Common divisor or HCF. The HCF stands for Highest common factor which is a second name of GCD. This progrram will calculate GCD of two positive inetegers using Improved version of Euclid’s algorithm – Succesive division method.
The Euclidean algorithm or Euclid’s Algorithm
The Euclidean algorithm is a method to find the GCD, that is the greatest common divisor of two positive integers, a and b.
Example of Finfing GCD of two integers by Euclid’s Algorith of Successive Division -Improved Version for Efficiency
Let a = 45 and b = 20
Step 1: If a<b then swap a and b. Since a>b, so ignore.
Step 2: Divide a by b, get remainder r. if rem=0 then print b is GCD & stop.
First Iteration: 45%20 ==> r = 5
Second Iteration after step 3: 20%5 ==> r = 0, therefore print b=5 is GCD & stop.
Step 3: Replace a by b and b by r. So that a=20 and b=5. Repeat step 2.
For two positive integers a and b, Euclid’d Theorem with Successive Division is as follows:
Step 1. If a<b, then swap the values of a and b. So that a must be greater than or equal to b.
Step 2. Divide a by b and get the remainder, r. If r=0, Print b as the GCD of a and b. & EXIT
Step 3. Replace a by b and replace b by r. Repeat step 2.