Hey guys!! Welcome to flower brackets blog. In this article we learn java find gcd and lcm using euclid’s algorithm.

#### Java find gcd and lcm using euclid’s algorithm

In the below java program user enters two numbers. These two numbers are divided and remainder will become divisor and previous divisor become dividend.

Repeat above process until remainder is zero. By doing this we get GCD as divisor. Similarly here’s the java program to find lcm of 2 numbers.

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

import java.util.Scanner;

public class GCDLCMEuclid

{

public static void main(String[] args)

{

GCDLCMEuclid obj = new GCDLCMEuclid();

System.out.println("Enter two numbers to find GCD : ");

Scanner sc = new Scanner(System.in);

long num1 = sc.nextLong();

long num2 = sc.nextLong();

obj.findGcd(num1, num2);

System.out.println("Enter two numbers to find LCM : ");

long g = sc.nextLong();

long d = sc.nextLong();

obj.findLcm(g, d);

sc.close();

}

void findGcd(long p, long q)

{

while(q > 0)

{

long temp = q;

q = p % q;

p = temp;

}

System.out.println("GCD : " + p);

}

void findLcm(long m, long n)

{

long a = m;

long b = n;

while(n > 0)

{

long temp = n;

n = m % n;

m = temp;

}

long gcd = m;

long lcm = (a * (b / gcd));

System.out.println("LCM : " + lcm);

}

}

**Output:**

Enter two numbers to find GCD : 4 34

GCD : 2

Enter two numbers to find LCM : 6 86

LCM : 258