求两数最大公约数和最小公倍数

今天下午第一节算法课留的小作业，顺手做了吧。
最大公约数和最小公倍数的概念就不解释了，暴力法也不说了不可取。
这里说下辗转相除法和更相减损法。

辗转相除法

辗转相除法，是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。
假设m > n，公式：gcd(m, n) = gcd(n, m mod n)
就是说m和n的最大公约数 = n和m/n的余数的，直到m mod n = 0，则n为最大公约数，而最小公倍数 = （mn）/gcd(m, n)
注：在代码中通常写做m / gcd(m,n) * n，防止mn过大爆可能会爆数据范围
上Java代码

	public static int gcd(int m, int n) {
        return m % n == 0 ? n : gcd(n, m % n);
    }

    public static void main(String[] args) {

       //最大公约数     5
        System.out.println(gcd(25, 15));
        //最小公倍数     75
        System.out.println(25 / gcd(25, 15) * 15);
    }

更相减损法

公式：gcd(m, n) = gcd(n, m-n)，直到m-n=0，则m或n就是最小公约数
输入两整数 m 和 n（m>=n）：

1）若m-n=0，则m（或n）即为两数的最大公约数

2）若m-n≠0，则m=n,n=m-n 再回去执行第1步

	public static int gcd2(int m, int n) {
        return m - n == 0 ? n : gcd2(n, m - n);
    }

    public static void main(String[] args) {
    
        //最大公约数     5
        System.out.println(gcd2(25, 15));
        //最小公倍数     75
        System.out.println(25 / gcd2(25, 15) * 15);
    }