Java Program - Find GCD of Two Numbers
GCD stands for Greatest Common Divisor. The GCD of two numbers is the largest number that divides both of them.
For example - GCD of 20 and 25 is 5, and GCD of 50 and 100 is 50.
Method 1: Using For Loop to find GCD of two numbers
In the example below, for loop is used to iterate the variable i from 1 to the smaller number. If both numbers are divisible by i, then it modifies the GCD and finally gives the GCD of two numbers.
public class MyClass { public static void main(String[] args) { int x = 50; int y = 100; int gcd = 1; int temp; if (x > y) { temp = x; x = y; y = temp; } for(int i = 1; i < (x+1); i++) { if (x%i == 0 && y%i == 0) gcd = i; } System.out.println("GCD of "+ x +" and "+ y +" is: "+ gcd); } }
The above code will give the following output:
GCD of 50 and 100 is: 50
Method 2: Using While Loop to find GCD of two numbers
In the example below, larger number is replaced by a number which is calculated by subtracting the smaller number from the larger number. The process is continued until the two numbers become equal which will be GCD of two numbers.
public class MyClass { public static void main(String[] args) { int p, q, x, y; p = x = 20; q = y = 25; while (x != y) { if (x > y) x = x - y; else y = y - x; } System.out.println("GCD of "+ p +" and "+ q +" is: "+ x); } }
The above code will give the following output:
GCD of 20 and 25 is: 5
Method 3: Using the recursive function to find GCD of two numbers
In the example below, recursive function is used. In this method, instead of using subtraction operator(as in above example), modulo operator is used. This method is also known as Euclidean algorithm.
public class MyClass { static int gcd(int x, int y) { if (y == 0) return x; return gcd(y, x%y); } public static void main(String[] args) { int x = 250; int y = 475; System.out.println("GCD of "+ x +" and "+ y +" is: "+ gcd(x,y)); } }
The above code will give the following output:
GCD of 250 and 475 is: 25
Recommended Pages
- Java Program - To Check Prime Number
- Java Program - Bubble Sort
- Java Program - Selection Sort
- Java Program - Maximum Subarray Sum
- Java Program - Reverse digits of a given Integer
- Java - Swap two numbers
- Java Program - Fibonacci Sequence
- Java Program - Insertion Sort
- Java Program - Find Factorial of a Number
- Java Program - Find HCF of Two Numbers
- Java Program - Merge Sort
- Java Program - Shell Sort
- Stack in Java
- Queue in Java
- Java Program - Find LCM of Two Numbers
- Java Program - To Check Whether a Number is Palindrome or Not
- Java Program - To Check Whether a String is Palindrome or Not
- Java Program - Heap Sort
- Java Program - Quick Sort
- Java - Swap Two Numbers without using Temporary Variable