HCF or GCD Program in Java and Python

Question:

Algorithm:

Explanation:

This program finds the HCF/GCD by checking possible common divisors. Since a common divisor cannot be greater than the smaller of the two numbers, the checking starts from the smaller number.

For each possible divisor, the program checks whether both numbers leave remainder 0. If both conditions are true, that number divides both inputs exactly.

The checking is done from higher to lower values. Therefore, the first common divisor found is automatically the highest common factor, and the loop can stop.

This approach is easy for students to trace because it follows the definition of HCF directly: the greatest number that divides both given numbers exactly.

Because the loop moves downward from the smaller number, the first divisor that divides both inputs is guaranteed to be the greatest one. This is why no later comparison is needed after it is found.

The loop variable itself is the candidate divisor. Each iteration performs two remainder checks, one for each input number, and the first candidate that satisfies both conditions is stored as the answer.

The HCF or GCD represents the largest number that divides both inputs exactly. Depending on the method used, the program may test possible factors or repeatedly use division. In either case, the result must satisfy two conditions: it divides the first number and it divides the second number. If factors are scanned, the largest valid factor is retained. If Euclid’s method is used, remainders reduce the problem until exact division is reached. The program’s variable updates preserve the common divisor relationship throughout.

Java Program:

/**
* The class Hcf inputs two numbers and finds their HCF
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
*/

import java.util.Scanner;
class Hcf
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the First no : ");
        int n1=sc.nextInt();
        System.out.print("Enter the Second no : ");
        int n2=sc.nextInt();
        int hcf=0;
        int min = Math.min(n1,n2);

        for(int i=min; i >= 1; i--)
        {
            if(n1%i == 0 && n2%i == 0)
            {
                hcf = i;
                break;
            }
        }
        System.out.print("\nThe hcf of "+n1+" and "+n2+" = "+hcf);
    }
}

Equivalent Python Program:

# Read the number and keep any required copy for digit or divisor processing.
# Loops and conditions implement the number-property test step by step.
# Display the result according to the flag/counter/calculated value.

n1 = int(input("Enter the first number: "))
n2 = int(input("Enter the second number: "))

minimum = min(n1, n2)
hcf = 0

for i in range(minimum, 0, -1):
    if n1 % i == 0 and n2 % i == 0:
        hcf = i
        break

print("The HCF of", n1, "and", n2, "=", hcf)

Output: