Write a Python Program to find GCD
The Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF), of two or more integers is the largest positive integer that divides all the given numbers without leaving a remainder. In other words, it’s the largest number that is a common divisor of the given numbers.
For example, the GCD of 8 and 12 is 4, because the divisors of 8 are 1, 2, and 4, and the divisors of 12 are 1, 2, 3, 4, and 6. The largest number that appears in both lists is 4.
Python Program to Calculate GCD:
Here’s a Python program that calculates the Greatest Common Divisor (GCD) of two numbers using the Euclidean algorithm:
def gcd(a, b):
a, b = b, a % b
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
gcd_result = gcd(num1, num2)
print("GCD of", num1, "and", num2, "is", gcd_result)
- The program defines a function gcd() that takes two numbers, a and b, and calculates their GCD using the Euclidean algorithm. The algorithm repeatedly takes the remainder of the larger number divided by the smaller number until the remainder becomes zero. The last non-zero remainder is the GCD.
- The user is prompted to enter two numbers using the input() function, and these numbers are converted to integers using the int() function. The input numbers are stored in the variables num1 and num2.
- The program calculates the GCD of the two input numbers by calling the gcd() function and passing num1 and num2 as arguments. The result is stored in the variable gcd_result.
- The print() function is used to display the calculated GCD along with the input numbers.
Enter first number: 48
Enter second number: 18
GCD of 48 and 18 is 6
In this example, if the user enters 48 and 18, the program calculates the GCD using the gcd() function and displays the result: “GCD of 48 and 18 is 6”.