GCD (HCF) of Two Numbers: flowchart, algorithm and program
This program reads two integers and prints their GCD (also called HCF), the largest number that divides both without a remainder. It uses the Euclidean algorithm: the GCD of a and b is the same as the GCD of b and a % b, so we repeat this until the remainder becomes 0.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Read a.
- Step 3: Read b.
- Step 4: If b != 0, go to step 5; otherwise go to step 8.
- Step 5: Set temp = b.
- Step 6: Set b = a % b.
- Step 7: Set a = temp. Go to step 4.
- Step 8: Print GCD = a.
- Step 9: Stop.
Pseudocode
BEGIN
READ a
READ b
WHILE b != 0 DO
temp ← b
b ← a % b
a ← temp
END WHILE
PRINT GCD = a
END
Program in C, Python and Java
GCD (HCF) of Two Numbers program in C
#include <stdio.h>
int main() {
int a, b, temp;
printf("Enter first number: ");
scanf("%d", &a);
printf("Enter second number: ");
scanf("%d", &b);
while (b != 0) {
temp = b;
b = a % b;
a = temp;
}
printf("GCD = %d\n", a);
return 0;
}GCD (HCF) of Two Numbers program in Python
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
while b != 0:
temp = b
b = a % b
a = temp
print("GCD =", a)GCD (HCF) of Two Numbers program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a, b, temp;
System.out.print("Enter first number: ");
a = sc.nextInt();
System.out.print("Enter second number: ");
b = sc.nextInt();
while (b != 0) {
temp = b;
b = a % b;
a = temp;
}
System.out.println("GCD = " + a);
}
}
Sample input: a = 48, b = 18
Output: Enter first number: Enter second number: GCD = 6
How it works
- Read the two numbers into a and b.
- The loop while (b != 0) keeps going as long as there is still a remainder to work with.
- Inside the loop, temp = b saves the old b. Then b = a % b stores the new remainder, and a = temp moves the old b into a. The temp variable is needed so the old value of b is not lost before a is updated.
- When b becomes 0, a holds the last non-zero remainder, which is the GCD.
- For a = 48 and b = 18 the pairs go (48, 18) -> (18, 12) -> (12, 6) -> (6, 0), so the program prints GCD = 6.
Dry run (trace table)
| Step | Line | Box | a | b | temp | Output |
|---|---|---|---|---|---|---|
| 1 | 3 | Start | ||||
| 2 | 6 | Read a | 48 | |||
| 3 | 8 | Read b | 48 | 18 | ||
| 4 | 10 | b != 0? | 48 | 18 | ||
| 5 | 11 | temp = b | 48 | 18 | 18 | |
| 6 | 12 | b = a % b | 48 | 12 | 18 | |
| 7 | 13 | a = temp | 18 | 12 | 18 | |
| 8 | 10 | b != 0? | 18 | 12 | 18 | |
| 9 | 11 | temp = b | 18 | 12 | 12 | |
| 10 | 12 | b = a % b | 18 | 6 | 12 | |
| 11 | 13 | a = temp | 12 | 6 | 12 | |
| 12 | 10 | b != 0? | 12 | 6 | 12 | |
| 13 | 11 | temp = b | 12 | 6 | 6 | |
| 14 | 12 | b = a % b | 12 | 0 | 6 | |
| 15 | 13 | a = temp | 6 | 0 | 6 | |
| 16 | 10 | b != 0? | 6 | 0 | 6 | |
| 17 | 16 | Print GCD = a | 6 | 0 | 6 | GCD = 6 |
| 18 | 17 | Stop | 6 | 0 | 6 |
Time and space complexity
Time: O(log(min(a, b))) · Space: O(1). Each iteration reduces the remainder at least by half every two steps, and only a few variables are used.
Common mistakes
- Updating a before saving b (writing a = b first and then b = a % b), which uses the wrong value and breaks the result. The temp variable prevents this.
- Printing b instead of a at the end. When the loop ends b is always 0, and the answer is in a.
- Using a loop condition like a != b with subtraction, or forgetting the case where b is 0 at the start. With the % version and while (b != 0), an input like (5, 0) correctly gives 5.
Viva questions
Q1. What does this program compute, and what is the name of the algorithm?
It computes the GCD (HCF) of two numbers, the largest number that divides both exactly. The method is Euclid's algorithm, which repeatedly replaces (a, b) with (b, a % b).
Q2. Why do you need the variable temp in lines 11-13?
Line 12 overwrites b, but the new a must be the old b. temp saves the old b first, so a = temp gives the right value. Without it, both a and b would end up holding the new remainder.
Q3. What does the condition b != 0 on line 10 check, and why does the loop stop there?
It checks whether the remainder is still non-zero. When b becomes 0, the last value of a divides the previous number exactly, so a is the GCD and no more steps are needed.
Q4. Trace the program for a = 48 and b = 18. What is printed?
(48, 18) becomes (18, 12), then (12, 6), then (6, 0). The loop stops and it prints GCD = 6.
Q5. What happens if the first number is smaller than the second, for example a = 12 and b = 18?
It still works. In the first pass 12 % 18 is 12, so (12, 18) becomes (18, 12), which swaps the numbers. After that it continues normally and gives 6.
Q6. What does the program print if b = 0, for example a = 5 and b = 0? What if both are 0?
If b is 0 the loop never runs and it prints a, which is 5. That is correct because gcd(a, 0) = a. If both are 0 it prints 0, which is a convention because the GCD of 0 and 0 is undefined.
Q7. What is the time complexity of this program?
It is O(log(min(a, b))). Each pair of steps at least halves the remainder, so the loop runs far fewer times than subtracting repeatedly would.
Q8. What would change if the user enters negative numbers, and how would you fix it?
In C, % can give a negative remainder, so the printed GCD might be negative. You can fix it by taking the absolute value of a and b with abs() before the loop, or by printing abs(a) at the end.
Q9. How would you change the program to find the LCM as well?
Save the product a*b before the loop, using long to avoid overflow. After the loop, LCM = (original a * original b) / GCD.
Frequently asked questions
How does the Euclidean algorithm find the GCD?
It replaces the pair (a, b) with (b, a % b) again and again. The GCD does not change at each step, and when the remainder reaches 0 the other number is the GCD.
What happens if the first number is smaller than the second?
It still works. In the first pass a % b equals a, so the two numbers swap places, and the algorithm continues normally from there.
What is the GCD if one of the numbers is 0?
The GCD is the other number. If b is 0 the loop never runs and the program prints a. If a is 0, one pass swaps the values and it prints b.