GCD of two numbers in Python

GCD of two numbers in Python

In the program, we will learn to find the GCD of two numbers that is Greatest Common Divisor.

The highest common factor (HCF) or Greatest Common Divisor (GCD) of two given numbers is the largest or greatest positive integer that divides the two number perfectly.

For example, here, we have two numbers 12 and 14

 Output: GCD is 2

Algorithm:

1. Define a function named gcd(a,b)
2. Initialize small =0 and gd =0
3. If condition is used to check if a is greater than b.
4. if true small==b, else small==a.
5. using for loop with range(1, small+1), check if((a % i == 0) and (b % i == 0))
6. if true gd=I and gd value is returned in variable t
7. Take a and b as input from the user.
8. The function gcd(a,b) is called with a and b as parameters passed in the function.
9. Print the value in the variable t.
10. Exit 

 

Code:

def gcd(a,b):
    small=0
    gd=0
    if a>b:
        small==b
    else:
        small==a
    for i in range(1, small+1):
        if((a % i == 0) and (b % i == 0)):
            gd=i
    return gd
a=int(input("Enter the first number: "))
b=int(input("Enter second number: "))
t=gcd(a,b)
print("GCD is:",t)

 

Output:

Enter the first number: 60
Enter second number: 48
GCD is: 12