求最小公倍数的两种算法（最大公约数的三种算法）

2024-06-30 13:16| 来源: 网络整理| 查看: 265

求最小公倍数的两种算法（最大公约数的三种算法）求两个正整数的最小公倍数是很常见的运算。比如，3和5的最小公倍是15。6和8的最小公倍数是24。下面的算法为给定的两个正整数求它的最小公倍数。 1.由最大公约数求最小公倍数

又称公式法，两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即可以利用辗转相除法（欧几里得算法）或者辗转相减（更相减损术）或者分解质因数法先求出最大公约数再用两数之积除以最大公约数得出最小公倍数。下面分析一下求最大公约数的三种算法。

（1）首先先复习一下什么是辗转相除法辗转相除：假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法（辗转相除法），是这样进行的： 1997 / 615 = 3 (余152) 615 / 152 = 4(余7) 152 / 7 = 21(余5) 7 / 5 = 1 (余2) 5 / 2 = 2 (余1) 2 / 1 = 2 (余0) 至此，最大公约数为1，以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数。

import java.util.Scanner; public class 最小公倍数 { public static int 辗转相除法(int a, int b) { if (a % b == 0) return b; else { return 辗转相除法(b, (a % b)); } } public static void main(String[] args){ Scanner scanner=new Scanner(System.in); System.out.println("请输入第一个数字"); int a=scanner.nextInt(); System.out.println("请输入第二个数字"); int b=scanner.nextInt(); if(a

【本文地址】

公司简介

联系我们