最小公倍数的两种算法（最大公约数三种算法）
求最小公倍数的两种算法（最大公约数的三种算法）
计算两组正整数值之间的最小公倍数值是一种普遍存在的数学操作。例如，在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，在持续执行被數與餘數之間的整數運算過程中當餘數歸零時當前運算式的被數即為目標結果
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<b) {//a,b需要先判断大小并排序
int c = a;
a = b;
b = c;
}
System.out.println("两数的最小公倍数为"+a*b/辗转相除法(a,b));
}
}（2）更相减损术的基础回顾
连续减法运算 ：
- 当a大于b时，将a更新为a与b的差值
- 若两数相等，则任一数值即代表最大公约数
- 当数值不等时需重新启动初始运算流程
以35与14为例，在运算过程中依次执行以下步骤：首步计算35减去14得到21；继而用21继续扣除14得出余数7；此时由于7小于当前被减数14需进行数值调换；随后以14作为被减数扣除7获得结果7；最终完成7-7=0的操作后即可确认最大公约数为7
该算法的核心特征在于通过持续执行大数减小数的操作，在反复迭代中逐步逼近两个整数的最大公约数值。
import java.util.Scanner;
public class 最小公倍数 {
public static int 更相减损术(int a,int b){
if(a<b) {
int c = a;
a = b;
b = c;
}
if (a == b) {
return a;
}
else {
return 更相减损术(a-b, 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();
System.out.println("两数的最小公倍数为"+a*b/更相减损术(a,b));
}
}（3）质因数分解 法
简要回顾：
以计算24与60的最大公约数为例。
首步操作为对两个数值进行质因数拆解。
24=2×2×2×3
60=2×3×2×5
随后需将两者的共有质因子进行相乘运算，即得出结果为12。
具体而言应当对各个数值逐一实施质因数拆分操作后，在所有数值中共通存在的基础素因子中选取全部元素并执行连乘运算所得到的结果值即代表这些整数值之间的最大公约数值。
import java.util.ArrayList;
import java.util.Scanner;
public class 分解质因子 {
public int f(int a,int b) {
//创建两个整数泛型数组
ArrayList<Integer> arrayList1 = new ArrayList<Integer>();
ArrayList<Integer> arrayList2 = new ArrayList<Integer>();
//分解第一个正整数质因子并放入数组1
for (int i = 2; a > 1; i++) {
for (; (a % i) == 0; a /= i) {
arrayList1.add(i);
}
}
//分解第二个正整数质因子并放入数组2
for (int j = 2; b > 1; j++) {
for (; (b % j) == 0; b /= j) {
arrayList2.add(j);
}
}
int button = 0;
int 最大公约数 = 1;
int temp = 0;
//查找相同质因子，找到相同因子存储后，删除两个数组中的相同因子
while (button < arrayList1.size()) {//数组访问从第零个开始
if (arrayList2.contains(arrayList1.get(button))) {//查找相同元素
最大公约数 = arrayList1.get(button) * 最大公约数;
arrayList2.remove(arrayList2.indexOf(arrayList1.get(button)));
arrayList1.remove(button);
button = temp;//每次删除完元素从temp开始查找
} else {temp = button += 1;//如果没相同元素temp+1
}
}
return 最大公约数;
}
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();
分解质因子 A=new 分解质因子();
int c=A.f(a,b);
System.out.println("最小公倍数为"+a*b/c);
}
}2.累加法
亦称为优化版本的穷举算法。令a与b为任意正整数。其最小公倍数值必然同时为两者之倍数。因此可随机选取其中一者作为循环参数起始点（以取定a为例），当该参数数值能够被另一数值整除时，则当前数值即为所求之最小公倍数值。否则需持续递增该参数单位量级
import java.util.Scanner;
public class 最小公倍数 {
public static int f(int a, int b)
{
int i;
for(i=a;;i+=a){
if(i%b==0) return i;
}
}
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();//此函数中a,b无需比较大小。
System.out.println(f(a,b));
}
}初次涉足此领域者，在实践过程中难免存在疏漏或欠妥之处，请诸位予以包容并提出宝贵意见。