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 gcd user enters two numbers. These two numbers are divided and remainder will become divisor and previous divisor become dividend.

Also read – polymorphism in java

Repeat above process until remainder is zero. By doing this we get java GCD as divisor.

Now let’s see gcd program in java using euclid’s algorithm java,

// gcd of two number 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 calculate 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 calculate LCM : "); long c = sc.nextLong(); long d = sc.nextLong(); obj.findLCM(c, d); sc.close(); } }

**Output:**

Please enter any two numbers to calculate GCD :

4

11

GCD is : 1

Please enter any two numbers to calculate LCM :

23

56

LCM is : 1288