题解 | #求最小公倍数#

1. 思路

两个数a,b的乘积等于两数的最大公约数x乘以最小公倍数y。

a * b = x * y

那么求解最小公倍数就可以从求解最大公约数开始。

最大公约数可以用辗转相除法来求解，其大致步骤如下：

先用小的一个数除大的一个数,得第一个余数；
再用第一个余数除小的一个数,得第二个余数；
又用第二个余数除第一个余数,得第三个余数；
这样逐次用后一个数去除前一个余数,直到余数是0为止.那么,最后一个除数就是所求的最大公约数（如果最后的除数是1,那么原来的两个数是互质数）.

2. 代码实现

import java.util.Scanner;

public class Main {
    /**
     * 采用递归的形式实现辗转相除法的算法
     * @param a 整数a
     * @param b 整数b
     * @return a和b的最大公约数
     */
    private static int gcd(int a, int b) {
        if (a % b == 0) return b;
        return gcd(b, a % b);
    }

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

C语言版本

#include <stdio.h>

int gcd(int a, int b)
{
    int temp;
    while (b)
    {
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

int main() {
   int a, b;
   scanf("%d %d", &a, &b);
    int res = (a * b) / gcd(a, b);
    printf("%d\n", res);
   return 0;
}