Java Program to Implement Euclid GCD Algorithm

This is a Java Program to implement Euclid’s GCD Algorithm. This is a program to find GCD (Greatest Common Divisor) of two numbers using Euclid’s Algorithm.

Algorithm is as follows :

function gcd(a, b)
    if b = 0
       return a
    else
       return gcd(b, a mod b)

Here is the source code of the Java program to implement Euclids GCD Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
/**
```

 ** Java Program to Implement Euclid GCD Algorithm

```
 **/
```
```
 
```
```
import java.util.Scanner;
```
```
 
```
```
/** Class EuclidGcd **/
```
```
public class EuclidGcd    
```
```
{
```
```
    /** Function to calculate gcd **/
```
```
    public long gcd(long p, long q)
```
```
    {
```
```
        if (p % q == 0)
```
```
            return q;
```
```
        return gcd(q, p % q);
```
```
    }
```
```
    /** Main function **/
```

    public static void main (String[] args)

```
    {
```

        Scanner scan = new Scanner(System.in);

        System.out.println("Euclid GCD Algorithm Test\n");

        /** Make an object of EuclidGcd class **/

```
        EuclidGcd eg = new EuclidGcd();
```
```
 
```
```
        /** Accept two integers **/
```

        System.out.println("Enter two integer numbers\n");

```
        long n1 = scan.nextLong();
```
```
        long n2 = scan.nextLong();
```

        /** Call function gcd of class EuclidGcd **/

```
        long gcd = eg.gcd(n1, n2);
```

        System.out.println("\nGCD of "+ n1 +" and "+ n2 +" = "+ gcd);

```
    }
```
```
}
```

Euclid GCD Algorithm Test
 
Enter two integer numbers
 
257184 800128
 
GCD of 257184 and 800128 = 28576

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

If you wish to look at all Java Programming examples, go to Java Programs.

« Prev - Java Program to Implement ConcurrentSkipListMap API

» Next - Java Program to Implement SimpeBindings API

Related Posts:

Recommended Articles: