ISC Practicals and Theory - GCD (Iterative Technique)

Updated 20 Oct 2026

The GCD (Greatest Common Divisor), also called the HCF (Highest Common Factor), of two numbers is the largest number that divides both of them exactly. This program finds it with Euclid's algorithm, using a while loop instead of recursion.

Definition

The GCD of two positive integers $a$ and $b$ is the greatest integer that divides both with no remainder. For example, the GCD of 48 and 18 is 6, and the GCD of 17 and 5 is 1.

Euclid's algorithm replaces the pair $(a, b)$ by $(b, a \bmod b)$ again and again. When the second number becomes 0, the first number is the GCD.

Algorithm

Start. Create an object of class GCDLoop in main.
accept() reads the two numbers into a and b.
display() checks the input. If a or b is zero or negative, print an error message and stop.
Otherwise display() calls hcf().
In hcf():
- Copy a into x and b into y, so the data members stay unchanged.
- While y is not 0: store x % y in r, set x = y, then set y = r.
- When the loop ends, return x.
Print the value returned by hcf().
Stop.

Program

The constructor sets a and b to 0, accept() takes the input, hcf() finds the GCD with a loop, and display() checks the input and prints the result.

import java.util.Scanner;
public class GCDLoop
{
    int a, b;

    GCDLoop()
    {
        a = 0;
        b = 0;
    }

    void accept()
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the first number: ");
        a = sc.nextInt();
        System.out.print("Enter the second number: ");
        b = sc.nextInt();
    }

    int hcf()
    {
        int x = a;
        int y = b;
        while (y != 0)
        {
            int r = x % y;
            x = y;
            y = r;
        }
        return x;
    }

    void display()
    {
        if (a <= 0 || b <= 0)
            System.out.println("Invalid input. Enter positive numbers only.");
        else
            System.out.println("GCD of " + a + " and " + b + " = " + hcf());
    }

    public static void main(String args[])
    {
        GCDLoop ob = new GCDLoop();
        ob.accept();
        ob.display();
    }
}

Variable description table

Variable	Data Type	Purpose
`a`	`int`	Data member that stores the first number
`b`	`int`	Data member that stores the second number
`sc`	`Scanner`	Object used to read the numbers from the keyboard
`x`	`int`	Local variable in `hcf()` that holds the current first number; at the end it holds the GCD
`y`	`int`	Local variable in `hcf()` that holds the current second number; the loop stops when it becomes 0
`r`	`int`	Local variable in the loop that holds the remainder `x % y`
`ob`	`GCDLoop`	Object of the class created in `main`
`args`	`String[]`	Command line arguments of `main`

Sample input and output

Sample 1

Enter the first number: 48
Enter the second number: 18
GCD of 48 and 18 = 6

Sample 2

Enter the first number: 17
Enter the second number: 5
GCD of 17 and 5 = 1

Sample 3

Enter the first number: -4
Enter the second number: 6
Invalid input. Enter positive numbers only.

Try it yourself

One value per line

Dry run

Take $a = 48$ and $b = 18$, so x = 48 and y = 18 before the loop.

Pass	x (before)	y (before)	r = x % y	x (after)	y (after)
1	48	18	12	18	12
2	18	12	6	12	6
3	12	6	0	6	0

Now y is 0, so the loop ends and hcf() returns 6. The output is GCD of 48 and 18 = 6, the same as the real run above.

Variations

GCD and LCM "Write a program to input two numbers and find their GCD and LCM."
Co-prime numbers "Input two numbers and check whether they are co-prime, that is, their GCD is 1."
Lowest terms "Input the numerator and denominator of a fraction and reduce it to its lowest terms using the GCD."