write a java program to check whether it is a GCD or not
Answers
Java Program to Find GCD of Two Numbers
In this section, we have covered different logics in Java programs to find GCD of two numbers.
Greatest Common Divisor: It is the highest number that completely divides two or more numbers. It is abbreviated for GCD. It is also known as the Greatest Common Factor (GCF) and the Highest Common Factor (HCF). It is used to simplify the fractions.
How to Find the Greatest Common Factor
- Write all the factors of each number.
- Select the common factors.
- Select the greatest number, as GCF.
Example: Find the GCF of 12 and 8.
Solution:
Factors of 12: 1, 2, 3, 4, 6, 12
Factors of 8: 1, 2, 4, 8
Common Factors: 1, 2, 4
Greatest Common Factor: 4
Hence, the GCF of 12 and 8 is 4.
Algorithm to Find GCD
- Declare two variables, say x and y.
- Run a loop for x and y from 1 to max of x and y.
- Check that the number divides both (x and y) numbers completely or not. If divides completely store it in a variable.
- Divide the stored number.
In Java, we can use the following ways to find the GCD of two numbers:
- Using Java for loop
- Using while loop
- Using User-Defined Method
- Using the Euclidean Algorithm
- Using Modulo Operator
Using Java for loop
In the following program, we have initialized two numbers x=12 and y=8. After that, we have used a for loop that runs from 1 to the smallest of both numbers. It executes until the condition i <= x && i <= y returns true. Inside the for loop, we have also used if statement that tests the condition (x%i==0 && y%i==0) and returns true if both conditions are satisfied. At last, we have store the value of i in the variable gcd and print the same gcd variable.
FindGCDExample1.java
public class FindGCDExample1
{
public static void main(String[] args)
{
//x and y are the numbers to find the GCF
int x = 12, y = 8, gcd = 1;
//running loop form 1 to the smallest of both numbers
for(int i = 1; i <= x && i <= y; i++)
{
//returns true if both conditions are satisfied
if(x%i==0 && y%i==0)
//storing the variable i in the variable gcd
gcd = i;
}
//prints the gcd
System.out.printf("GCD of %d and %d is: %d", x, y, gcd);
}
}