Java programs to find the HCF or GCD of two numbers:
Let’s learn how to find the HCF of two numbers in Java. HCF also called GCD. The full form of HCF is Greatest common denominator and the full form of GCD is Greatest common denominator.
The HCF or GCD of two or more numbers the greatest common divisor is not zero. For example the GCD by 8 And 12 is 4. Because
- The factors of 8 Are 1, 2, 4, 8
- The factors of 12 Are 1, 2, 3, 4, 6, 12
The highest common factor is 4.
Let me explain the algorithm before we start writing the program.
Algorithm to find the HCF or GCD of two numbers:
The program takes the numbers as input from the user.
- Take the numbers as user input and assign the values to two different variables.
- Initialize one variable every time HCF value.
- Perform one loop 1 to the smaller value of the two numbers.
- Inside the loop, check whether the current variable used in the loop can divide both numbers or not. If so, assign this value to the HCF variable.
- Once the loop ends, the HCF variable contains the required value HCF or GCD.
Basically, we’re using a loop of 1 to the smaller number and dividing both numbers by the loop variable to get the GCD or HCF. The largest value that can divide both numbers is the GCD of the two digits.
Method 1: Java program to find the GCD or HCF using a for loop:
The Java program below uses the algorithm above to do the GCD:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int first, second, hcf = 1;
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the first number: ");
first = scanner.nextInt();
System.out.println("Enter the second number: ");
second = scanner.nextInt();
for (int i = 2; i <= first || i <= second; i++) {
if (first % i == 0 && second % i == 0) {
hcf = i;
}
}
System.out.println("HCF: " + hcf);
}
}
- The integer variables First And second are used to hold the first and second numbers, hcf is used to hold the calculated value HCF. It is initialized as 1.
- This program uses a Scanner object to read the user input numbers.
- The for run Runs from I = 2. We have already defined it hcf as 1. So we need to find any value that can both divide the numbers and be greater than 1.
- The value of hcf is updated as i can divide both numbers.
- At the end of the program the calculated value is printed HCF value.
Example result:
Enter the first number:
4
Enter the second number:
12
HCF: 4
Method 2: Java program to find HCF or GCD using a while loop:
We can easily convert the above program to one repeat loop instead of a for run. The only change we need is to initialize the variable i before the loop starts and increment its value at the end of each iteration of the loop.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int first, second, hcf = 1, i = 2;
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the first number: ");
first = scanner.nextInt();
System.out.println("Enter the second number: ");
second = scanner.nextInt();
while (i <= first || i <= second) {
if (first % i == 0 && second % i == 0) {
hcf = i;
}
i++;
}
System.out.println("HCF: " + hcf);
}
}
This program will print similar results.
Method 3: Java program to find HCF with repeated subtraction:
This is another way to find HCF. We run a while loop until the numbers are equal. On each iteration, it subtracts the smaller number from the larger number and assigns it to the larger number variable.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int first, second;
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the first number: ");
first = scanner.nextInt();
System.out.println("Enter the second number: ");
second = scanner.nextInt();
while (first != second) {
if (first > second)
first = first - second;
else
second = second - first;
}
System.out.println("HCF: " + first);
}
}
The number variable contains the requirement HCF.
Method 4: By using the Euclidean algorithm:
This is one of the most efficient algorithms to find the GCD.
import java.util.Scanner;
public class Main {
static int findGCD(int first, int second){
if(second == 0)
return first;
return findGCD(second , first % second);
}
public static void main(String[] args) {
int first, second;
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the first number: ");
first = scanner.nextInt();
System.out.println("Enter the second number: ");
second = scanner.nextInt();
System.out.println("GCD: " + findGCD(first, second));
}
}
This algorithm is based on a similar fact to the previous algorithm. If we keep subtracting the smaller number from the larger number, we get the GCD once both are equal. We can also divide the first number by the second number and assign the remainder to the second number and assign the original second number to the first number. When the second song will be 0the first number contains the GCD value. This program will also produce similar results.
C# Tip: DO NOT use nameof to value constants
Programming in C# involves making numerous decisions to ensure code efficiency and maintainability. One common aspect is dealing with constants,…
Can we run a Java program without the main method
Can we run a Java program without the main method? The mainly method is executed when we execute a class in…
Java program to calculate students grades in 2 different ways
Java program to calculate students grades: In this post we will learn different ways to calculate the figure from a student…
C# Tip: LINQ’s Enumerable.Range to generate a range of consecutive numbers
When you need to generate a series of numbers in ascending order, you can simply use a while loop with…
Java String charAt method explanation with examples
Java String charAt method: The signAt method of Java string is used to find a character at a given index. This…
3 Ways to Convert System.nanoTime to Seconds in Java
How to convert System.nanoTime to seconds in Java: In this post we will learn how to convert System.nanoTime Unpleasant seconds in…
of course like your website but you have to check the spelling on several of your posts A number of them are rife with spelling issues and I in finding it very troublesome to inform the reality on the other hand I will certainly come back again
My brother suggested I might like this website He was totally right This post actually made my day You cannt imagine just how much time I had spent for this information Thanks