WAP to find the GCD (HCF) of two numbers in Java
What is GCD (HCF) ?
- GCD (Greatest Common Divisor) or HCF (Highest Common Factor) is the largest number that divides two or more numbers without a remainder.
-
For example:
For 12 and 18:- Divisors of 12: 1, 2, 3, 4, 6, 12
- Divisors of 18: 1, 2, 3, 6, 9, 18
- GCD (HCF) = 6 (the largest common divisor)
Logical Steps:
- Take two numbers to find their GCD.
- Use a loop to find the common divisors of both numbers.
- Start from 1 and loop up to the smaller of the two numbers.
- Check divisibility of both numbers by the current loop number.
- Track the largest number that divides both numbers without a remainder.
- Return the largest common divisor as the GCD (HCF).
Programs:
-
Below is the simple program:
public class GcdOfTwoNumbers { public static void main(String[] args) { int no1 = 12, no2 = 15; int gcd = 1; for (int i = 1; i <= no1 && i <= no2; i++) { if (no1 % i == 0 && no2 % i == 0) { gcd = i; } } System.out.println("GCD: " + gcd); } }Output:
GCD: 3
-
Below is the program by taking user input:
import java.util.Scanner; public class GcdOfTwoNumbers { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("Enter no1: "); int no1 = scanner.nextInt(); System.out.print("Enter no2: "); int no2 = scanner.nextInt(); int gcd = 1; for (int i = 1; i <= no1 && i <= no2; i++) { if (no1 % i == 0 && no2 % i == 0) { gcd = i; } } System.out.println("GCD: " + gcd); } }Output:
Enter no1: 56 Enter no2: 72 GCD: 8
Program Explanation
-
Initialization and Variables:
-
The program starts by taking two integers,
no1andno2, from the user. - A variable gcd is initialized to 1 to store the greatest common divisor.
-
The program starts by taking two integers,
-
Iteration to Find GCD:
-
A
forloop runs from 1 to the smaller of no1 and no2. -
In each iteration:
-
Check divisibility of both numbers by the loop variable
i. -
If both numbers are divisible by
i, assignito the gcd variable (update it with the latest common divisor).
-
Check divisibility of both numbers by the loop variable
-
A
-
Output:
- After the loop completes, gcd will hold the largest number that divides both numbers without a remainder.
- The result is printed as GCD: [value].
Help Us Get Better Every Day
Your feedback helps us grow! If there's anything we can fix or improve, please let us know.
We’re here to make our tutorials better based on your thoughts and suggestions.
