算法训练 5-1最小公倍数

问题描述

　　编写一函数lcm，求两个正整数的最小公倍数。

样例输入

  一个满足题目要求的输入范例。 
 
例： 
 
3 5

样例输出

  与上面的样例输入对应的输出。 
 
例：

数据规模和约定

　　输入数据中每一个数的范围。
　　例：两个数都小于65536。

import java.util.Scanner;

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

	private static int lcm(int a, int b) {
		// TODO Auto-generated method stub
		int g = gcd(a,b);
		return a*b/g;
	}

	private static int gcd(int a, int b) {
		// TODO Auto-generated method stub
		if(b == 0)
			return a;
		else
			return gcd(b,a%b);
	}

}

思路：最小公倍数LCM=两个数的乘积/最大公约数GCD，因此就转化成了求解最大公约数的问题。

（1）利用欧几里德算法（辗转相除法）求出两个正整数a、b的GCD：

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

把递归换成循环：

int gcd(int a, int b) {
    int r;
    while (b != 0) {
        r = a % b; 
        a = b;
        b = r;
    }
    return a;
}

还有一个出自《九章算数》的更相减损术

以及Stein算法

（2）扩展欧几里德算法用来求解模线性方程(组)：

ax+by=gcd(a,b)

参考博客：https://blog.csdn.net/Holmofy/article/details/76401074

作者写的特别详细系统。

秒客网

算法训练 5-1最小公倍数

相关文章