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

  1. Step 1: Start.
  2. Step 2: Read a.
  3. Step 3: Read b.
  4. Step 4: If b != 0, go to step 5; otherwise go to step 8.
  5. Step 5: Set temp = b.
  6. Step 6: Set b = a % b.
  7. Step 7: Set a = temp. Go to step 4.
  8. Step 8: Print GCD = a.
  9. 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)

StepLineBoxabtempOutput
13Start
26Read a48
38Read b4818
410b != 0?4818
511temp = b481818
612b = a % b481218
713a = temp181218
810b != 0?181218
911temp = b181212
1012b = a % b18612
1113a = temp12612
1210b != 0?12612
1311temp = b1266
1412b = a % b1206
1513a = temp606
1610b != 0?606
1716Print GCD = a606GCD = 6
1817Stop606

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.

More programs

← All programs

Try AI Flowchart free →