Euclid's algorithm Java Programming

The greatest common divisor (gcd) of two positive integers is the largest integer that divides evenly into both of them. For example, the greatest common divisor of 102 and 68 is 34 since both 102 and 68 are multiples of 34, but no integer larger than 34 divides evenly into 102 and 68. We can efficiently compute the gcd using the following property, which holds for positive integers p and q:

If p > q, the gcd of p and q is the same as the gcd of q and p % q.

The static method gcd() in Euclid.java is a compact recursive function whose reduction step is based on this property.

gcd(1440, 408) 
   gcd(408, 216) 
      gcd(216, 192) 
         gcd(192, 24)
            gcd(24, 0)
               return 24
            return 24 
         return 24 
      return 24 
   return 24 

Euclid.java

/*************************************************************************

 *  Compilation:  javac Euclid.java

 *  Execution:    java Euclid p q

 * 

 *  Reads two command-line arguments p and q and computes the greatest

 *  common divisor of p and q using Euclid's algorithm.

 *

 *  Remarks

 *  -----------

 *    - may return the negative of the gcd if p is negative

 *

 *************************************************************************/

public class Euclid {

    // recursive implementation

    public static int gcd(int p, int q) {

        if (q == 0) return p;

        else return gcd(q, p % q);

    }

    // non-recursive implementation

    public static int gcd2(int p, int q) {

        while (q != 0) {

            int temp = q;

            q = p % q;

            p = temp;

        }

        return p;

    }

    public static void main(String[] args) {

        int p = Integer.parseInt(args[0]);

        int q = Integer.parseInt(args[1]);

        int d  = gcd(p, q);

        int d2 = gcd2(p, q);

        System.out.println("gcd(" + p + ", " + q + ") = " + d);

        System.out.println("gcd(" + p + ", " + q + ") = " + d2);

    }

}

Copyright © 2000–2010, Robert Sedgewick and Kevin Wayne.
Last updated: Wed Feb 9 09:05:37 EST 2011.