Python GCD Program by Successive Division

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.

Python GCD Program by Successive Division

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