GCD of Two Numbers in Java
![Java Course - Mastering the Fundamentals](https://www.scaler.com/topics/images/instructor-tarun.webp)
The Greatest Common Divisor (GCD), or Highest Common Factor (HCF), is the largest number that divides two numbers without a remainder. It can be calculated using methods like the naive loop approach, the Euclidean algorithm by subtraction, and the Euclidean algorithm with modulo operation. The Greatest Common Divisor (GCD) reflects common factors in prime factorizations.
Algorithm to Find GCD
The algorithm to find the GCD of two numbers that comes intuitively to most people is to check the divisibility of both the numbers in a loop from numbers 1 to , then return the biggest number that divides both of them, thus, GCD of two numbers.
We are going till because the GCD of a and b cannot be greater than the minimum of a and b.
Proof: Let's assume a is smaller than b. Let x > a be a common divisor of a and b. This is not possible as the divisor of any number cannot be greater than itself.
How to Find the Greatest Common Factor?
In Java, we can find the GCD (Greatest Common Factor) of two numbers using the ways discussed below:
Find GCD of Two Numbers Using for Loop and if Statement
We can find the GCD of two numbers in Java using a for loop and an if condition from checking the greatest integer dividing both the numbers by iterating from 1 to .
Steps of the Algorithm:
- Take two numbers (a and b) as input from the user to find their GCD.
- Initialize a variable to store the GCD with an initial value of .
- Check if a or b is equal to 0, if yes, store the non-zero number in the GCD variable. If this condition satisifies, step 4 will be skipped.
- Iterate from 1 to and check if the number divides both a and b, if yes, then store it in GCD.
- Print the GCD.
Example:
Source Code
Output:
Explanation:
In the above example, we are finding the GCD of two numbers (a and b) by iterating from 1 to and checking the divisibility of the numbers, the greatest number that divides both a and b is the GCD of a and b.
Complexity Analysis:
-
Time Complexity: In this algorithm, we are iterating from 1 to min(a,b) in a for loop, so the time complexity will be O(min(a,b)).
-
Space Complexity: The space complexity here is constant as we are using constant space.
Find GCD of Two Numbers Using While Loop and if Statement
We can use a while loop and an if condition to find out the GCD of two numbers in Java using the above algorithm. Steps of the Algorithm:
- Take two numbers (a and b) as input from the user to find their GCD.
- Initialize a variable to store the GCD with an initial value of .
- Check if a or b is equal to 0, if yes, store the non-zero number in the GCD variable. If this condition satisifies, step 6 will be skipped.
- Initialize a variable i = 1 for the while loop.
- Run a while loop unless the following condition is false: .
- In each iteration, check if the number divides both and b, if yes, then store it in GCD. Increment i.
- After the end of while loop, print the GCD.
Examples:
Source Code
Output:
Explanation:
In the above example, we are finding the GCD of two numbers (a and b) using a while loop iterating as long as , we are checking if a and b are divisible by i or not in each iteration, if yes, then we will store the value of in GCD. The final value of the GCD after the end of the while loop will be our result.
Complexity Analysis:
-
Time Complexity: In this algorithm, we are iterating from 1 to min(a,b) in a for loop, so the time complexity will be O(min(a,b)).
-
Space Complexity: The space complexity here is constant.
Find GCD of Both Positive and Negative Numbers
The GCD is always positive irrespective of the sign of the input numbers. If the given number is negative, we will simply ignore its "-" sign using the abs() function. After making the negative numbers positive, we can find the GCD of two numbers (positive or negative) number using the for loop and an if condition algorithm by checking the divisibility of both the numbers (a and b) iterating from 1 to .
Note: The abs() function returns the absolute value of an integer which is always positive. For example, abs(-5) will be equal to 5.
Steps of the Algorithm:
- Take two numbers (a and b) as input from the user to find their GCD.
- Initialize a variable to store the GCD with an initial value of .
- Assign .
- Check if a or b is equal to 0, if yes, store the non-zero number in the GCD variable. If this condition satisifies, step 5 will be skipped.
- Iterate from 1 to min(a,b) and check if the number divides both a and b, if yes, then store it in GCD.
- Print the GCD.
Example:
Source Code
Output:
Explanation:
In the above example, we are finding the GCD of two numbers (a and b) which maybe positive or negative by first assigning them their absolute values (using the Math abs() function) and then iterating from 1 to min(a,b) and checking the divisibility of the numbers, the greatest number that divides both a and b is the GCD of a and b.
Complexity Analysis:
- Time Complexity: In this algorithm, we are iterating from 1 to in a for loop, so the time complexity will be O(min(a,b)).
- Space Complexity: The space complexity here is constant.
Find GCD of Two Numbers Using User-Defined Method
Using a user-defined method to find the GCD of two numbers is a smarter way than writing the whole implementation in the main(), as we can use the method as a utility method to use it as many times as we want just by calling it, enhancing readability and maintenance of the program. We will be using the for loop and if condition method (discussed above) in the user-defined function.
Steps of the Algorithm:
- Create a user-defined method called GCD() that accepts two integer parameters (a and b).
- Inside the function, initialize a variable to store the GCD with an initial value of .
- Assign and .
- Check if b or a is equal to , if yes, store the non-zero number in the GCD variable. If this condition satisifies, step 5 will be skipped.
- Iterate from 1 to min(a, b) and check if the number divides both a and b, if yes, then store it in GCD.
- Return GCD from the GCD() function.
- Print the GCD in the main() function.
Example:
Source Code
Output:
Explanation:
In the above example, we are finding the GCD of two numbers (a and b) by calling a user-defined method called GCD() which assigns the numbers their absolute values and iterates from to min(a,b) to check if divides and , if yes, GCD variable will store i, after the end of the while loop, the GCD variable will be equal to the greatest common divisor of a and b.
Complexity Analysis:
-
Time Complexity: In this algorithm, we are iterating from 1 to in a for loop, so the time complexity will be O(min(a,b)).
-
Space Complexity: The space complexity here is constant.
Find GCD of Two Numbers Using Euclidean Algorithm by Subtraction
To find the GCD of two numbers using recursion, we will be using the principle , its proof is discussed in the section "Find GCD of two numbers Using the Euclidean Algorithm" above.
Steps of the Algorithm
- Check if , if yes, return b.
- Check if , if yes, return a.
- Check if , if yes, return a.
- Check if if yes, call GCD() function using the arguments and recursively, otherwise call GCD() function using the arguments and
Example:
Source Code
Output:
Explanation:
In the above example, we are finding the GCD of two numbers (a and b) using recursion following the principle that assuming . If the base cases are not followed we will recursively call the GCD() function. GCD(a, b - a) if else GCD(a - b, b).
Complexity Analysis:
-
Time Complexity: In this algorithm, the number of steps are linear, for e.g. , in which we will subtract from in each recursion, so the time complexity will be .
-
Space Complexity: The space complexity here is because the space complexity in a recursive function is equal to the maximum depth of the call stack.
Find GCD of Two Numbers Using the Euclidean Algorithm
The Euclidean algorithm is an efficient way to calculate the GCD of two numbers. It is named after the ancient Greek mathematician Euclid who first described this algorithm in his books called Elements in 300 BC.
This algorithm is based on the fact that is equal to as subtracting a smaller number from a larger number doesn't change their GCD. So if we keep subtracting the larger of the two, we will end up with their GCD.
The Eulidean Algorithm states that if and , where is the quotient and is the remainder, then .
As discussed above, we already know that , we can repeatedly apply this rule to itself to obtain, .
As , it is proved that .
Steps of the Algorithm
- Take two numbers (a and b) as input from the user to find their GCD.
- Store the greater number among and in , and the other one in y.
- Initialize a variable r used to store the GCD of a and b.
- Iterate in a while loop while
- In each iteration, assign , , and .
- After the end of the while loop, return the value r, that is the GCD of a and b.
Example:
Source Code
Output:
Explanation:
In the above example, we are finding the GCD of two numbers (a and b) using the Euclidean algorithm which states that where a > b. In this algorithm, we are using a while loop in which we are assigning , , and till . The value of r after the end of the loop will be equal to the GCD of a and b.
Complexity Analysis:
-
Time Complexity: In this algorithm, we are iterating in the while loop till We are reducing to in each iteration, so the time complexity will be .For in-depth analysis of time complexity of Euclidean Algorithm, follow Euclidean Algorithm article from Scaler Topics.
-
Space Complexity: The space complexity here is constant.
Find GCD of Two Numbers Using Recursion
We can find the GCD of two numbers using a modulo operator by the help of Euclidean Algorithm, which states that , where r is the remainder after dividing a by b. The proof of the Euclidean Algorithm has been discussed in the above section
Steps of the Algorithm
- In the user-defined method GCD(), check if , if yes, return .
- If , recursively call the GCD() function by passing the parameters and , i.e .
Example:
Source Code
Output:
In the above example, we are implementing the Euclidean algorithm using recursion to find the GCD of two numbers. The base case here is: if , then return , otherwise, recursively call .
Complexity Analysis:
-
Time Complexity: In this algorithm, we are recursively calling reducing the second parameter by in each function call, so the maximum number of steps required to reduce b to 0 will be: .
-
Space Complexity: In recursion, the space complexity is equal to the maximum depth of the call stack, i.e .
Conclusion
- GCD (Greatest Common Divisor) is also known as HCF (Highest Common Factor).
- GCD of two numbers is the greatest positive integer that completely divides both the given numbers.
- The time complexity of the Naive approach to finding the GCD of two numbers is .
- The time and space complexity of the Euclidean algorithm by Subtraction to find the GCD of two numbers is
- The time complexity of the Euclidean algorithm to find the GCD of two numbers is .