gcd_recursion.java

来自「用递归方法求最大公因数！！！不是什么难的程序」· Java 代码 · 共 46 行

//【习3.24】  将辗转相除法求两个整数的最大公因数gcd(a,b)用递归方法实现。

public class GCD_recursion
{
    public static int gcd(int a,int b)           //返回a,b的最大公因数
    {
        if (b==0)
            return a;
            
        if (a<0)
            return gcd(-a,b);
            
        if (b<0)
            return gcd(a,-b);
            
        return gcd(b, a%b);
    }

    public static int gcd(int a,int b,int c)     //返回a,b,c的最大公因数
    {
        return gcd(gcd(a,b),c);
    }

    public static int multiple(int a,int b)      //返回a,b的最小公倍数
    {
        return a*b/gcd(a,b);
    }

    public static void main(String args[]) 
    {
        int a=12,b=18,c=27;
        System.out.println("gcd("+a+","+b+")="+gcd(a,b));
        System.out.println("gcd("+(-a)+","+b+")="+gcd(-a,b));
        System.out.println("gcd("+a+","+b+","+c+")="+gcd(a,b,c));
        System.out.println("multiple("+a+","+b+")="+multiple(a,b));
    }
}

/*
程序运行结果如下：
gcd(12,18)=6
gcd(-12,18)=6
gcd(12,18,27)=3
multiple(12,18)=36

*/