GCD Program in Java
The GCD program in Java outputs the greatest common divisor of the given numbers. GCD is an acronym that stands for Greatest Common Divisor. It is also known as HCF (Highest Common Factor). GCD is the highest number that divides two or more than two given numbers completely. There are different ways to find the GCD.
Using Java for Loop
Filename: GCDExample.java
Output:
Explanation: The GCD of any two numbers is always less than or equal smallest of the given numbers, which serve the condition of our for-loop. The for-loop runs from 1 to the minimum of the given numbers. In each iteration, we check whether the given numbers are divisible by the loop variable i or not. If the variable i divides both the numbers, we update the value of the ans variable else the variable ans remains the same.
Using Java while Loop
Filename: GCDExample1.java
Output:
Explanation: We are reducing the given numbers by subtracting the smaller number from the larger one and continue to do so until both the numbers are equal.
Using Java while Loop
Filename: GCDExample1.java
Output:
Explanation: We are reducing the given numbers by subtracting the smaller number from the larger one and continue to do so until both the numbers are equal.
Using Factors of the Given Numbers
Filename: GCDExample2.java
Output:
Explanation: In the above approach, we are finding all the factors of the given numbers and storing those factors in the lists. Then we are converting those lists into integer arrays. The first integer array contains all the factors of the first input number, and the second integer array contains the factors of the second input number. Since we have found the factors from one to the number itself, therefore, the integer arrays contain all the factors in ascending order. Now, we have applied the two-pointer approach to find the common elements, as the arrays are sorted. The highest common element is our answer that we are displaying on the console.
Using Euclid’s Algorithm
Euclid’s algorithm is the best approach to find the GCD as it takes less time as compared to other approaches. The algorithm says:
The following program implements the above algorithm to find the GCD of given numbers.
Filename: GCDExample3.java
Output:
So far, we have only discussed the GCD of the two given numbers. However, it is also possible to find the GCD of more than two numbers. The following program illustrates the same.
Filename: GCDExample4.java
Output:
Explanation: We are iterating over every element of the input array and recursively calculating GCD using Euclid’s algorithm.
Note: In all the above examples, we have discussed about the non-negative elements. However, GCD of negative numbers do exist. In fact, the GCD is independent of the sign of the input numbers, i.e., GCD(-a, -b) = GCD(-a, b) = GCD(a, -b) = GCD(a, b).
Designed by Elegant Themes | Powered by WordPress