Python Practice › Basic Programs › Program 36
HCF (GCD) of two numbers
Write a Python program to find the HCF (highest common factor, also called GCD) of two numbers.
Input
48 and 36
Output
HCF: 12
Approach
- Euclid’s algorithm: replace (a, b) with (b, a % b) until b is 0; then a is the HCF.
Solution 1: Euclid’s algorithm
a, b = 48, 36while b: a, b = b, a % bprint("HCF:", a)Output
HCF: 12
Line by line
Line 2
The loop runs while b is not zero.
Line 3
(48, 36) → (36, 12) → (12, 0), so the HCF is 12.
Solution 2: math.gcd
import mathprint(math.gcd(48, 36))Output
12
Learn the concept
New to this topic? Read the lesson, then come back.