Euclidean algorithm (Java)

From LiteratePrograms

Other implementations: C | Erlang | Forth | Haskell | Java | Java, recursive | OCaml | Prolog | Python | Scala | Standard ML

The Java implementation of the Euclidean algorithm is remarkably similar to the C implementation of the Euclidean algorithm.

<<Euclidean algorithm loop>>=
while (b != 0) 
{
    int m = a % b;
    a = b;
    b = m;
}
return a;

We only need to ensure that a > b by swapping the inputs at the start of the function, if necessary:

<<Euclidean algorithm>>=
public static int gcd(int a, int b)
{
    if (b > a)
    {
        int temp = a;
        a = b;
        b = temp;
    }
    Euclidean algorithm loop
}

Download code