COS126

• Download Part2.java

/*******************************************************************************
 * Name: Robert Sedgewick
 * NetId: rs
 * Precept: P255
 *
 * Description: Takes two positive integers p and q from standard input; prints
 *              out their greatest common factor.
 *
 * Dependencies: StdIn.java, StdOut.java
 *
 *****************************************************************************/

public class Part2 {

    // recursive method to find gcf of p and q
    public static int gcf(int p, int q) {
        // base case
        if (p == q) return p;

        // call gcd with smaller and abs(difference)
        int smaller = Math.min(p, q);
        int difference = Math.abs(p - q);
        return gcf(smaller, difference);
    }

    public static void main(String[] args) {
        // input x, y from standard input
        int x = StdIn.readInt();
        int y = StdIn.readInt();

        // print their greatest common factor
        int g = gcf(x, y);
        StdOut.println(g);
    }
}