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.