Here we will write a Python program to find the GCD of two numbers using euclidean algorithm.

GCD (Greatest Common Divisor) : In mathematics , the greatest common divisor ( gcd ) of two or more integers , which are not all zero, is the largest positive integer that divides each of the integers.

Here we will see for two values.

As example :

GCD of 8 and 12 is 4
8%4 = 0 
12%4 = 0

So 4 is the largest positive integer that divides each of the integers.

Euclidean algorithm: an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder .

 

def calculate_gcd(a,b):
    while(b):
        a, b = b, a%b
    return a 

Here we will loop until b becomes 0. And in each iteration, we place the value of a in b and the remainder (a % b) in b, simultaneously. When a becomes zero, we have GCD in a.

Run

$ python gcd.py

Sample Input:

8 
12

Sample Output

GCD: 4

I hope i was clear enough to you. if got any better solution please share in the comment bellow.

Thanks.