Euclidean Algorithm with Example in Java

Euclidean Algorithm is a way to finding GCD (Greatest Common Divisor) of two integers quickly. If we have two integers (A, B) and we want to find out gcd(A,B) then Euclidean Algorithm is one of the best technique.
Application Of Euclidean Algorithm

• For finding GCD of two numbers
• Euclidean Rythms : developed by GodFried Tourssaint in 2004 and described in a 2005 paper "The Euclidean Algorithm generates Traditional Musical Rhythms.

The Algorithm

If A=0 then GCD(A,B)=B since GCD(0,B) and we can stop

If B=0 then GCD(A,B)=A since GCD(A,0) and we can stop

Example:

import java.util.*;
public class EuclideanAlgorithm {
    public static void main(String arg[]) {
        Scanner sb = new Scanner(System.in);
        int a, b, q, r;
        System.out.println("Enter value of A :");
        a = sb.nextInt();
        System.out.println("Enter value of B :");
        b = sb.nextInt();
        if (a == 0) {
            System.out.println("gcd(" + a + "," + b + ")=" + b + "");
        } else if (b == 0) {
            System.out.println("gcd(" + a + "," + b + ")=" + a + "");
        } else {
            System.out.print("gcd(" + a + "," + b + ")=");
            if (a > b) {
                r = a % b;
                q = a / b;
                while (r > 0) {
                    a = b * q + r;
                    a = b;
                    b = r;
                    r = a % b;
                    q = a / b;
                }
                System.out.println(b);
            } else {
                r = b % a;
                q = b / a;
                while (r > 0) {
                    b = a * q + r;
                    b = a;
                    a = r;
                    r = b % a;
                    q = b / a;
                }
                System.out.println(a);
            }
        }
    }
}