最大公约数&最小公倍数

概念

最大公约数

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。

最小公倍数

两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。

思路

递归求最大公约数；由最大公约数求最小公倍数！求x与y的最小公倍数，从正整数1开始整数循环与最大公约数相乘，直至乘积可以分别被x与y除尽，则乘积就是最小公倍数！

Code

public class gcd_lcm {
    static int gcd(int x,int y) {
        int z;
        while(y!=0) {
            z=y;
            y=x%y;
            x=z;
        }
        return x;
    }
    static int gcd0(int x,int y) {
        x%=y;
        return x!=0?gcd0(y,x):y;
    }
    static int lcm(int x,int y) {
        int z=gcd(x,y);
        for(int i=1;;i++) {
            if(z*i%x==0&&z*i%y==0)
                return z*i;
        }
    }
    public static void main(String[] args) {
        Scanner as=new Scanner(System.in);
        int x,y;
        while(as.hasNext()) {
            x=as.nextInt();
            y=as.nextInt();
            System.out.println(x+","+"的最大公约数为："+gcd(x,y)+"="+gcd(x,y)+";最小公倍数为："+lcm(x, y));
        }
    }

}

解析

gcd(int x,int y)函数是循环求最大公约数，gcd0(int x,int y)函数是递归求最大公约数，lcm(int x,int y)是求最小公倍数