Java Program to find GCD and LCM of Two Numbers Using Euclid's Algorithm

This is a Java Program to find GCD and LCM of Two Numbers Using Euclid’s Algorithm. Euclid’s Algorithmis an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest numerical algorithms in common use.

We divide the two numbers entered by the user and remainder become divisor while previous divisor become dividend now. This process repeat until the remainder become zero and we get the GCD as divisor which gives remainder as zero. LCM is a little trickier, but probably the best approach is reduction by the GCD, which can be similarly iterated.

Here is the source code of the Java Program to find GCD and LCM of Two Numbers Using Euclid’s Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
import java.util.Scanner;
```
```
public class Euclid
```
```
{
```
```
    void gcd(long a, long b)
```
```
    {
```
```
        while (b > 0)
```
```
        {
```
```
             long temp = b;
```

             b = a % b; // % is remainder

```
             a = temp;
```
```
        }
```

        System.out.println("GCD is "+a);

```
    }
```
```
    void lcm(long a, long b)
```
```
    {
```
```
        long x = a;
```
```
        long y = b;
```
```
        while (b > 0)
```
```
        {
```
```
            long temp = b;
```

            b = a % b; // % is remainder

```
            a = temp;
```
```
        }
```
```
        long gcd = a;
```
```
        long lcm = (x * (y / gcd));
```

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

```
    }
```

    public static void main(String... a)

```
    {
```
```
        Euclid abc = new  Euclid();
```

        System.out.println("Enter any two numbers to calculate GCD");

        Scanner s = new Scanner(System.in);

```
        long x = s.nextLong();
```
```
        long y = s.nextLong();
```
```
        abc.gcd(x, y);
```

        System.out.println("Enter any two numbers to calculate LCM");

```
        long l = s.nextLong();
```
```
        long m = s.nextLong();
```
```
        abc.lcm(l, m);
```
```
    }
```
```
}
```

Output:

$ javac Euclid.java
$ java Euclid
 
Enter any two numbers to calculate GCD
6 50
GCD is 2
Enter any two numbers to calculate LCM
11 17
LCM is 187

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

« Prev - Java Program to Find Missing Numbers in Array

» Next - Java Program to Illustrate the Use of HashCode() Method

Related Posts:

Practice Programming MCQs
Practice BCA MCQs
Apply for Java Internship
Check Java Books
Apply for Computer Science Internship

Recommended Articles: