求两个数的最大公约数（Euclid算法）

求两个数的最大公约数（Euclid算法）

求两个数 p 和 q 的最大公约数（greatest common divisor，gcd），利用性质

如果 p > q, p 和 q 的最大公约数 = q 和 （p % q）的最大公约数。

证明：见 http://blog.csdn.net/niushuai666/article/details/7278027

public class Euclid{

    // recursive inplementation

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

        if(q == 0) return p;

        else

        {

            StdOut.println( q + " " + p % q);

            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);

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

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

    }

}

运行结果