Java Program to Implement Euclid GCD Algorithm using Recursion

The Euclidean algorithm calculates the greatest common divisor (GCD) of two number a and b. The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder. Synonyms for the GCD include the greatest common factor (GCF), the highest common factor (HCF), the highest common divisor (HCD), and the greatest common measure (GCM).

The Algorithm

The Euclidean Algorithm for finding GCD(A,B) is as follows:
  • If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop.
  • If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.
  • Write A in quotient remainder form (A = B⋅Q + R)
  • Find GCD(B,R) using the Euclidean Algorithm since GCD(A,B) = GCD(B,R)
           // Function to return gcd of a and b
        int gcd(int a, int b)
          {
             if (a == 0)
                 return b;
             return gcd(b%a, a);
           }
This is a program to find GCD (Greatest Common Divisor) of two numbers using Euclid’s Algorithm.
<pre>import java.util.Scanner;

/**
 * Java Program to Implement Euclid GCD Algorithm using Recursion
 * Created by sani kamal on 07-May-17.
 */
public class GCDEuclid {
    //main function
    public static void main(String[] args) {
        GCDEuclid gcdeu = new GCDEuclid();
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter number1:");
        int num1 = sc.nextInt();
        System.out.println("Enter number2:");
        int num2 = sc.nextInt();
        System.out.println("GCD of " + num1 + " and " + num2 + " is:" + gcdeu.gcd(num1, num2));


    }

    // This function calculate GCD
    private int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);

    }
}</pre>
The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
"C:\Program Files\Java\jdk1.8.0_65\bin\java" -Didea.launcher.port=7536 "-Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 2016.1.3\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_65\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_65\jre\lib\rt.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\out\production\JavaByExample;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\laf-plugin-7.2.1.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\laf-widget-6.3.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\substance-7.2.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\trident.jar.zip;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\xmlbeans-2.6.0.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\poi-ooxml-schemas-3.14-20160307.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\poi-ooxml-3.14-20160307.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\poi-3.14-20160307.jar;C:\Users\THINKSONU\IdeaProjects\JavaByExample\lib\mail.jar;C:\Program Files (x86)\JetBrains\IntelliJ IDEA 2016.1.3\lib\idea_rt.jar" com.intellij.rt.execution.application.AppMain com.muktangon.net.recursion.GCDEuclid
Enter number1:
5
Enter number2:
25
GCD of 5 and 25 is:5

Process finished with exit code 0
Advertisements

One thought on “Java Program to Implement Euclid GCD Algorithm using Recursion

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s