欧几里得定理及辗转相除法,辗转相除法的数学原理

问题描述: 两个数a,b,要求求得这两个数的最大公约数和最小公倍数.

解题思路:

辗转相除法(ssdzs定理)思想:一个数,能整除数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);}}

编译运行:

查阅相关github代码请移步:https://github.com/striner/javaCode/blob/master/gcd%26lcm