欧几里得算法

                                    基于辗转相除法求最大公约数

(1)p=0,q=0 无最大公约数
(2)p=0,q≠0 最大公约数为q
(3)p≠0,q=0 最大公约数为p
(4)p≠0,q≠0 最大公约数可通过辗转相除取余数转化为(2)(3)这样的情况来求解

//递归版，非递归用循环
public class Euclid {
    public static void main(String[] args) {
        System.out.println(euclid(16,8));
    }
    public static int euclid(int p,int q) {
        int r=0,min=0;
        if(p==0||q==0) {
            if(p==0&&q==0)
                return -1;
            else if(p==0)
                return q;
            else if(q==0) {
                return p;
            }
        }
        else {
            if(p<q)
            {
                r = q % p;
                min = p;
            }
            else
            {
                r = p % q;
                min =q;
            }       
        }
        return euclid(min,r);
    }
}

//非递归
public class Euclid {
    public static void main(String[] args) {
        System.out.println(euclid(16,8));
    }
    public static int euclid(int p,int q) {
        int r=0,min=0;
        while(p!=0&&q!=0) {
            if(p<q)
            {
                r = q % p;
                min = p;
            }
            else
            {
                r = p % q;
                min =q;
            }
            p=min;
            q=r;
        }
        if(p==0&&q==0)
            return -1;
        else if(p==0)
            return q;
        else if(q==0) 
            return p;
        return -1;              //为了返回值强行加，突然感觉返回值好烦人
    }
}