经典算法之辗转相除法(欧几里得定理)

striner

于 2018-04-01 18:27:00 发布

阅读量6.6k

点赞数

本文链接：https://blog.csdn.net/striner/article/details/79780185

版权

本文介绍了利用辗转相除法（欧几里得定理）求解两个数的最大公因数（GCD）的思路和Java代码实现，并提供了相关GitHub代码链接。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

问题描述:

两个数a,b,要求求得这两个数的最大公约数和最小公倍数.

解题思路:

辗转相除法(欧几里得定理)思想:一个数,能整除数a和数b,那么这个数一定可以整除(a-b),即gcd(a, b) = gcd(a, a%b);

基于算法基本定理: 质因数分解的一致性

代码实现:

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
 	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int a = input.nextInt();
		int b = input.nextInt();
		System.out.println(gcd(a, b));  //求a和b的最大公约数
		System.out.println(lcm(a, b));  //求a和b的最小公倍数
		
		input.close();
	}

	public static int lcm(int a, int b) {
		
		return a * b / gcd(a, b);
	}

	public static int gcd(int a, int b) {

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

编译运行:

最低0.47元/天解锁文章