用java求最大公约数-c求约数

Java实现求解两个正整数的最大公约数和最小公倍数

公约数 ：公因数，显示着若干个整数之间的数论关系。如果一个数同时是几个数的约数，称这个数为它们的“公因数”；公约数中最大一个的称为最大公因数。

公倍数 ：公倍数，显示着若干个整数之间的数论关系。如果一个数同时是几个数的倍数，称这个数为它们的“公倍数”；公倍数中最小一个的称为最小公倍数。

普通思路 ：

①求解最大公约数：

显然用java求最大公约数，最大公约数小于等于两正整数中较小的一个，同时满足公约(m % i == 0 && n % i == 0)，故使用for循环从两正整数中较小的一个开始依次减少进行求解，当第一次找到符合条件(m % i == 0 && n % i == 0)便break用java求最大公约数，输出的结果即所求最大公约数。

②求解最小公倍数：

同理，最小公倍数需满足大于两正整数中较小的那个同时不大于两正整数的乘积，使用for循环同上即可求解。

import java.util.Scanner;
//求最大公约数和最小公倍数
/**
 * @auther  turbo
 * @date 2020-08-14 19:41
 */
/*
  输入两个正整数m和n，求其最大公约数和最小公倍数
 */
public class CommonDivisorMultipleTest {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入第一个正整数：");
        int m = scan.nextInt();
        System.out.println("请输入第二个正整数：");
        int n = scan.nextInt();
        //求两个数的最大公约数：
        //获取两个数中的最小值
        int min = (m < n) ? m : n ;
        for (int i = min ; i >= 1 ; i--) {
            if (m % i == 0 && n % i == 0){
                System.out.println("两个数的最大公约数是："+i);
                break;//一旦在循环中执行到break,就跳出循环
            }
        }
        //求两个数的最小公倍数：
        //获取两个数中的最大值
        int max = (m > n) ? m : n ;
        for (int t = max; t <= m * n ; t++) {
            if (t % m == 0 && t % n == 0){
                System.out.println("两个数的最小公倍数是:"+t);
                break;//一旦在循环中执行到break,就跳出循环
            }
        }
    }
}

用 辗转相除法 求解，具体代码如下：

int GCD(int a, int b) {
	return a % b == 0 ? b : GCD(b, a % b);
}
int LCM(int a, int b) { 
	return a * b / GCD(a, b);
}