# 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.

1. `/**`
2. ` ** Java Program to Implement Euclid GCD Algorithm`
3. ` **/`
4. ` `
5. `import java.util.Scanner;`
6. ` `
7. `/** Class EuclidGcd **/`
8. `public class EuclidGcd    `
9. `{`
10. `    /** Function to calculate gcd **/`
11. `    public long gcd(long p, long q)`
12. `    {`
13. `        if (p % q == 0)`
14. `            return q;`
15. `        return gcd(q, p % q);`
16. `    }`
17. `    /** Main function **/`
18. `    public static void main (String[] args) `
19. `    {`
20. `        Scanner scan = new Scanner(System.in);`
21. `        System.out.println("Euclid GCD Algorithm Test\n");`
22. `        /** Make an object of EuclidGcd class **/`
23. `        EuclidGcd eg = new EuclidGcd();`
24. ` `
25. `        /** Accept two integers **/`
26. `        System.out.println("Enter two integer numbers\n");`
27. `        long n1 = scan.nextLong();`
28. `        long n2 = scan.nextLong();`
29. `        /** Call function gcd of class EuclidGcd **/`
30. `        long gcd = eg.gcd(n1, n2);`
31. `        System.out.println("\nGCD of "+ n1 +" and "+ n2 +" = "+ gcd);`
32. `    }`
33. `}`

```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.

If you find any mistake above, kindly email to [email protected]