Let’s learn java program find GCD and LCM of two numbers using euclid’s algorithm.
Java program find GCD and LCM of two numbers using euclid’s algorithm
In the below java program user enters two numbers using nextLong() method of Scanner class.
These two numbers are divided and remainder will become divisor and previous divisor become dividend.

Repeat above steps until remainder is zero. By doing this we get GCD as divisor.
Also read – java program to find lcm of two numbers
Now let’s see java program to find gcd and lcm using euclid’s algorithm.
import java.util.Scanner; public class GCDLCMEuclid { // gcd java void findGCD(long num1, long num2) { while(num2 > 0) { long temp = num2; num2 = num1 % num2; num1 = temp; } System.out.println("GCD is : " + num1); } // lcm java void findLCM(long num1, long num2) { long a = num1; long b = num2; while(num2 > 0) { long temp = num2; num2 = num1 % num2; num1 = temp; } long gcd = num1; long lcm = (a * (b / gcd)); System.out.println("LCM is : " + lcm); } public static void main(String[] args) { GCDLCMEuclid obj = new GCDLCMEuclid(); System.out.println("Please enter any two numbers to find GCD : "); Scanner sc = new Scanner(System.in); long a = sc.nextLong(); long b = sc.nextLong(); obj.findGCD(a, b); System.out.println("Please enter any two numbers to find LCM : "); long c = sc.nextLong(); long d = sc.nextLong(); obj.findLCM(c, d); sc.close(); } }
Output:
Please enter any two numbers to find GCD :
4
11
GCD is : 1
Please enter any two numbers to find LCM :
23
56
LCM is : 1288
GCD of two numbers in java using recursion
Let’s find gcd of two numbers in java using recursion.
public class GCDUsingRecursion { public static void main(String[] args) { int number1 = 898, number2 = 90; int gcd = gcdRecursion(number1, number2); System.out.println("G.C.D of " + number1 + " and " + number2 + " is " + gcd); } public static int gcdRecursion(int num1, int num2) { if(num2 != 0) { return gcdRecursion(num2, num1 % num2); } else { return num1; } } }
Output:
G.C.D of 898 and 90 is 2
extended euclidean algorithm java
public class ExtendedEuclideanAlgorithm { public static void main(String[] args) { int a = 1, b = 1; int number1 = 84, number2 = 24; int gcd = extendedEuclidean(number1, number2, a, b); System.out.println("GCD of extended euclidean algorithm java (" + number1 + ", " + number2 + ") = " + gcd); } public static int extendedEuclidean(int x, int y, int num1, int num2) { if(x == 0) { num1 = 0; num2 = 1; return y; } int p = 1, r = 1; int gcd = extendedEuclidean(y % x, x, p, r); // results of recursive call num1 = r - (y / x) * p; num2 = p; return gcd; } }
Output:
GCD of extended euclidean algorithm java (84, 24) = 12
gcd of n numbers in java
Let’s learn gcd of n numbers in java.
public class GCDOfNNumbers { public static void main(String[] args) { int[] arrNumbers = {25, 46, 61, 88}; int output = gcdNumbers(arrNumbers[0], arrNumbers[1]); for(int a = 2; a < arrNumbers.length; a++) { output = gcdNumbers(output, arrNumbers[a]); } System.out.println("gcd of n numbers in java: " + output); } public static int gcdNumbers(int x, int y) { int result = 0; while(y > 0) { int temp = y; y = x % y; x = temp; result = x; } return result; } }
Output:
gcd of n numbers in java: 1
gcd of three numbers in java
Here’s gcd of three numbers in java.
import java.util.Scanner; public class GCDOfThreeNumbers { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Please enter first number: "); int number1 = sc.nextInt(); System.out.println("Please enter second number: "); int number2 = sc.nextInt(); System.out.println("Please enter third number: "); int number3 = sc.nextInt(); int gcdNumbers = GCDOfThreeNumbers.findGCD(number1, number2, number3); System.out.println("GCD of three numbers " + number1 + ", " + number2 + " and " + number3 + " is: " + gcdNumbers); sc.close(); } public static int findGCD(int x, int y) { if(y == 0) { return x; } else { return findGCD(y, x % y); } } public static int findGCD(int x, int y, int z) { return findGCD(findGCD(x, y), z); } }
Output:
Please enter first number: 12
Please enter second number: 48
Please enter third number: 84
GCD of three numbers 12, 48 and 84 is: 12
gcd of two numbers in java
GCD of two numbers is the largest positive number that divides both numbers without remainder.
For example:
10 – 1, 2, 5
15 – 1, 3, 5
GCD of 10 and 15 is 5.
Click here to learn program on gcd of two numbers in java.
lcm and gcd of two numbers in java
Here’s the program on lcm and gcd of two numbers in java.
import java.util.Scanner; public class LCMAndGCD { static int findGcd(int num1, int num2) { int rem = 0, a, b; a = (num1 > num2) ? num1 : num2; b = (num1 < num2) ? num1 : num2; rem = b; while(a % b != 0) { rem = a % b; a = b; b = rem; } return rem; } static int findLcm(int num1, int num2) { int a; a = (num1 > num2) ? num1 : num2; while(true) { if(a % num1 == 0 && a % num2 == 0) return a; ++a; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Please enter two numbers to find lcm and gcd: "); int p = sc.nextInt(); int q = sc.nextInt(); System.out.println("GCD of two numbers is: " + findGcd(p, q)); System.out.println("LCM of two numbers is: " + findLcm(p, q)); sc.close(); } }
Output:
Please enter two numbers to find lcm and gcd:
48
36
GCD of two numbers is: 12
LCM of two numbers is: 144
Also read – lcm of two numbers in java