求最小公倍数的两种算法(最大公约数的三种算法) )求两个正整数的最小公倍数是常见的运算。 例如，3和5的最小公倍是15。 6和8的最小公倍数是24。
下面的算法对给定的两个正整数求其最小公倍数。 1 .根据最大公约数求出最小公倍数也称为公式法。 可以使用两个数的乘积等于这两个数的最大公约数与最小公倍数的积(即，转相除法(wndppx算法)或转相减法)相位减损技术)或分解质因数法来获得最大公约数，然后将两个数的乘积除以最大公约数来获得最小公倍数。 分析一下求最大公约数的三种算法。
)1)首先复习什么是辗转相除法辗转相除
如果需要获得1997和615两个正整数的最大公约数，使用wndppx算法(换相除法) :
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； 公共类最小公倍数{公共静态int换相除法(int a，int b ) ) if ) a%b==0)返回b； else { return换相除法(b，(a % b )； } publicstaticvoidmain (string [ ] args )扫描仪扫描仪=new scanner ) system.in )； System.out.println ('请输入第一个数字)； int a=scanner.nextInt (； system.out.println ('请输入第二个数字)； int b=scanner.nextInt (； if(ab )//a，b首先判断大小，int c=a； a=b； b=c； } System.out.println (两数的最小公倍数为(a*b/滚动相除) a，b ) )； ()2)辗转相减简单复习辗转相减
如果是ab，则a=a-b如果a=b，则a (或b )是两个数的最大公约数，如果ab，则为了返回第一步求出35和14两个正整数的最大公约数，使用更相位减损术(换相减法)
35-14=21
21-14=7，此时7小于14，更换一次以14为被减数
即14-7=7
7-7=0这样也求出了最大公约数7
其特色是做一系列减法，从大的数中减去小数，求出最大公约数。
import java.util.Scanner； 公共类最小公倍数{公共静态int更相位减损术(int a，int b ) if(ab ) int a； a=b； b=c； (if ) a==b ) ) {返回a； (else )回输更相减损术(a-b，b )； } publicstaticvoidmain (string [ ] args )扫描仪扫描仪=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的最大公约数。
步骤1 :分解24和60。
24=2X2X2X3
60=2X3X2X5
步骤2:24和60的最大公约数乘以24和60共有的公共因子，即2X2X3=12。
即，将各数据分别分解为质因数，取出各数据中的所有公开质因数并相乘，得到的积就是这些数据的最大公约数。
import java.util.ArrayList； import java.uti
l.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,b的倍数，所以任选a，b一个作为循环变量初始值（假设选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)); }}新手上路，因能力有限，若有不足之处还望大家海涵！