a，b的最大公约数为gcd（a，b），最小公倍数的公式为：
$图片说明$
此题说是正数，所以绝对值无所谓了。我们可以发现题目带了‘递归’的标签，那么就用递归来实现gcd，既是面向题目编程，又方便了自己，一举两得。

gcd的算法是根据Euclidean algorithm来的，拿维基百科的例子来说：

$图片说明$

计算a = 1071和b = 462的最大公约数的过程如下：从1071中不断减去462直到小于462（可以减2次，即商q0 = 2），余数是147：

1071 = 2 × 462 + 147.

然后从462中不断减去147直到小于147（可以减3次，即q1 = 3），余数是21：

462 = 3 × 147 + 21.

再从147中不断减去21直到小于21（可以减7次，即q2 = 7），没有余数：

147 = 7 × 21 + 0.

此时，余数是0，所以1071和462的最大公约数是21。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            int b = in.nextInt();
            int lcm = a*b / gcd(a,b);
            System.out.println(lcm);
        }
    }

    public static int gcd(int a, int b) {
            if (b==0) return a;
            return gcd(b,a%b);
    }
}

求最小公倍数

全站热榜

创作者周榜