ISC Practicals and Theory - GCD

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, written as a recursive method.

Definition

The GCD of two positive integers $a$ and $b$ is the greatest integer that divides both $a$ and $b$ with no remainder.

The factors of 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24, 48 and of 18 are 1, 2, 3, 6, 9, 18. The largest common factor is 6, so the GCD of 48 and 18 is 6.
17 and 5 have only 1 in common, so their GCD is 1.

Euclid's algorithm uses the fact that the GCD of $a$ and $b$ is the same as the GCD of $b$ and the remainder of $a \div b$. The process stops when the remainder becomes 0, and the last non-zero number is the GCD.

Algorithm

Start. Create an object of class GCD 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(a, b).
In hcf(x, y):
- If y is 0, return x (base case).
- Otherwise return hcf(y, x % y) (recursive call, with the remainder replacing the second number).
Print the value returned by hcf.
Stop.

Program

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

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

    GCD()
    {
        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, int y)
    {
        if (y == 0)
            return x;
        return hcf(y, x % y);
    }

    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(a, b));
    }

    public static void main(String args[])
    {
        GCD ob = new GCD();
        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`	Parameter of `hcf()`: the larger (or current first) number in each call
`y`	`int`	Parameter of `hcf()`: the current second number; the recursion stops when it becomes 0
`ob`	`GCD`	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: 0
Enter the second number: 5
Invalid input. Enter positive numbers only.

Try it yourself

One value per line

Dry run

Take $a = 48$ and $b = 18$. The call hcf(48, 18) works as follows.

Call	x	y	y == 0?	x % y	Next call or result
1	48	18	No	12	`hcf(18, 12)`
2	18	12	No	6	`hcf(12, 6)`
3	12	6	No	0	`hcf(6, 0)`
4	6	0	Yes	-	returns 6

The value 6 is returned back through calls 3, 2 and 1, so 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."