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.

# Write a Python program to find # GCD of two numbers using Successive Division # method from Euclidean Theorm or # Euclid's theorem # # Author: www.EasyCodeBook.com (c) n1= int(input('Enter the first number=')) n2= int(input('Enter the second number=')) a = n1 b = n2 if a<b: # if a is smaller then exchange a,b a, b = b, a while (a%b) != 0: rem = a % b a = b b = rem print('GCD of',n1,'and',n2,'is:',b)

### The Output of the Python program GCD by Successive division

Enter the first number=210 Enter the second number=45 GCD of 210 and 45 is: 15 Another sample run: Enter the first number=24 Enter the second number=18 GCD of 24 and 18 is: 6