Python Program to find GCD

January 19, 2021 11:55 am IST

You are Here:

What is Greatest Common Divisor?

A largest number that exactly divides two or more integers.

In general, Greatest Common Divisor (GCD) is otherwise called as Greatest Common Factor (GCF) or Highest Common Factor (HCF)

Tips: It is recommended to use our online GCD calculator for better understanding.

Examples

The following table provides few examples of GCD of the given numbers.

Numbers	GCD
4, 10	2
6, 5	1
15, 30 , 45	15

GCD of Two Numbers

In the following example, we will find the GCD of the given two numbers (45, 90).

Example

Python Compiler

num1 = 45 num2 = 90 gcd = 1 min = (num1 < num2) and num1 or num2; for i in range(1, min+1): if((num1 % i == 0) and (num2 % i == 0)): gcd = i print("GCD of %d and %d: %d" % (num1, num2, gcd))

Output

GCD of 45 and 90: 45

GCD of any Two Given Numbers

In the following example, we will find the GCD of any two given numbers.

Example

Python Compiler

num1 = int(input("Enter (int) num1 = ")) num2 = int(input("Enter (int) num1 = ")) gcd = 1 min = (num1 < num2) and num1 or num2; for i in range(1, min+1): if((num1 % i == 0) and (num2 % i == 0)): gcd = i print("\nGCD of %d and %d: %d" % (num1, num2, gcd))