Python Program to Compute GCD
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.
Comments
Leave a comment
You are not LoggedIn but you can comment as an anonymous user which requires manual approval. For better experience please Login.