GCD (HCF)
Find the greatest common divisor (HCF) of two numbers using Euclidean algorithm.
IntermediateTopic: Module 3: Loop Programs
Java GCD (HCF) Program
This program helps you to learn the fundamental structure and syntax of Java programming.
import java.util.Scanner;
public class Main {
private static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter first number: ");
int a = sc.nextInt();
System.out.print("Enter second number: ");
int b = sc.nextInt();
System.out.println("GCD = " + gcd(a, b));
sc.close();
}
}Output
Enter first number: 24 Enter second number: 36 GCD = 12
Understanding GCD (HCF)
We repeatedly replace (a, b) with (b, a % b) until b becomes 0.
Note: To write and run Java programs, you need to set up the local environment on your computer. Refer to the complete article Setting up Java Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your Java programs.