C求最小公倍数：公式法 vs 短除法 vs 辗转相除法 vs 分解质因数法

大家好，欢迎来到IT知识分享网。

目录

1.最小公倍数

2.常用的最小公倍数的算法

（1）公式法：

（2）短除法：

（3）辗转相除法：

（4）分解质因数法：

1.最小公倍数

        最小公倍数（Least Common Multiple，LCM）是两个或多个整数共有的最小的能被整除的数。例如，12 和 18 的最小公倍数是 36。

2.常用的最小公倍数的算法

        不同的方法有不同的适用场景和计算效率，可以根据具体的需求和情况选择合适的方法。

（1）公式法：

        最小公倍数等于两数之积除以最大公约数。即 LCM(a, b) = a * b / GCD(a, b)。

// 公式法求最小公倍数 namespace _139 { class Program { /// <summary> /// 计算最小公倍数 /// </summary> public static float LeastComMultiple(int a, int b) { int gcd = GreatestComDivisor(a, b); return a * b / gcd; } /// <summary> /// 计算最大公约数 /// </summary> public static int GreatestComDivisor(int a, int b) { while (b != 0) { int remainder = a % b; a = b; b = remainder; } return a; } static void Main(string[] args) { ArgumentNullException.ThrowIfNull(args); while (true) { Console.Write("请输入第一个数："); int n1 = Convert.ToInt32(Console.ReadLine());//记录第一个数 Console.Write("请输入第二个数："); int n2 = Convert.ToInt32(Console.ReadLine());//记录第二个数 if (n1 * n2 != 0) //判断两个数中的一个是否为0 { Console.WriteLine("{0}和{1}的最小公倍数为{2}", n1, n2, LeastComMultiple(n1, n2));//输出最小公倍数 } else { Console.WriteLine("这两个数不能为0。"); } } } } } //运行结果： /* 请输入第一个数：12 请输入第二个数：18 12和18的最小公倍数为36 请输入第一个数：9 请输入第二个数：6 9和6的最小公倍数为18 请输入第一个数： */

（2）短除法：

        将两个数从小到大排列，然后进行短除法，直到余数为 0，最后的除数就是最大公约数，然后用两数之积除以最大公约数即可得到最小公倍数。

// 采用短除法的实现求两个整数最小公倍数的算法 namespace _139_1 { class Program { public static int LeastComMultiple(int a, int b) { int smaller = Math.Min(a, b); int larger = Math.Max(a, b); int lcm = smaller; int i = smaller + 1; while (i <= larger) { if (lcm % i == 0 && larger % i == 0) { lcm = i; } i++; } return lcm * larger / GreatestComDivisor(lcm, larger); } public static int GreatestComDivisor(int a, int b) { while (b != 0) { int remainder = a % b; a = b; b = remainder; } return a; } static void Main(string[] args) { ArgumentNullException.ThrowIfNull(args); while (true) { Console.Write("请输入第一个数："); int n1 = Convert.ToInt32(Console.ReadLine());//记录第一个数 Console.Write("请输入第二个数："); int n2 = Convert.ToInt32(Console.ReadLine());//记录第二个数 if (n1 * n2 != 0) //判断两个数中的一个是否为0 { Console.WriteLine("{0}和{1}的最小公倍数为{2}", n1, n2, LeastComMultiple(n1, n2));//输出最小公倍数 } else { Console.WriteLine("这两个数不能为0。"); } } } } } //运行结果： /* 请输入第一个数：12 请输入第二个数：18 12和18的最小公倍数为36 请输入第一个数：9 请输入第二个数：6 9和6的最小公倍数为18 请输入第一个数： */

（3）辗转相除法：

        也称为更相减损术，是一种用于求最大公约数的算法，可以通过将求得的最大公约数代入公式 LCM(a, b) = a * b / GCD(a, b) 中求得最小公倍数。

// 辗转相除法求两个整数最小公倍数的算法实现 namespace _139_2 { class Program { public static int LeastComMultiple(int a, int b) { int gcd = GCD(a, b); return a * b / gcd; } public static int GCD(int a, int b) { if (b == 0) { return a; } else { return GCD(b, a % b); } } static void Main(string[] args) { ArgumentNullException.ThrowIfNull(args); while (true) { Console.Write("请输入第一个数："); int n1 = Convert.ToInt32(Console.ReadLine());//记录第一个数 Console.Write("请输入第二个数："); int n2 = Convert.ToInt32(Console.ReadLine());//记录第二个数 if (n1 * n2 != 0) //判断两个数中的一个是否为0 { Console.WriteLine("{0}和{1}的最小公倍数为{2}", n1, n2, LeastComMultiple(n1, n2));//输出最小公倍数 } else { Console.WriteLine("这两个数不能为0。"); } } } } } //运行结果： /* 请输入第一个数：12 请输入第二个数：18 12和18的最小公倍数为36 请输入第一个数：9 请输入第二个数：6 9和6的最小公倍数为18 请输入第一个数： */

        辗转相除法是一种用于求最大公约数的算法，其基本思想是用较大的数除以较小的数，然后用得到的余数和较小的数再进行同样的操作，直到余数为 0，此时的除数就是最大公约数。在上述代码中，我们首先使用辗转相除法计算出两个数的最大公约数，然后用两个数的乘积除以最大公约数即可得到最小公倍数。 

（4）分解质因数法：

        将两个数分解为质因数，然后取各质因数的最高次幂相乘即可得到最小公倍数。例如，12 = 2^2 * 3，18 = 2 * 3^2，所以 12 和 18 的最小公倍数为 2^2 * 3^2 = 36。

// 利用分解质因数法求两个整数最小公倍数的算法实现 namespace _139_3 { class Program { public static int LeastComMultiple(int a, int b) { List<int> factorsA = GetPrimeFactors(a); List<int> factorsB = GetPrimeFactors(b); factorsA.Sort(); factorsB.Sort(); int lcm = 1; int i = 0; while (i < factorsA.Count && i < factorsB.Count) { if (factorsA[i] == factorsB[i]) { lcm *= factorsA[i]; i++; } else if (factorsA[i] < factorsB[i]) { lcm *= factorsA[i]; factorsA.RemoveAt(i); } else { lcm *= factorsB[i]; factorsB.RemoveAt(i); } } while (i < factorsA.Count) { lcm *= factorsA[i]; i++; } while (i < factorsB.Count) { lcm *= factorsB[i]; i++; } return lcm; } public static List<int> GetPrimeFactors(int n) { List<int> factors = []; while (n % 2 == 0) { factors.Add(2); n /= 2; } for (int i = 3; i <= Math.Sqrt(n); i += 2) { while (n % i == 0) { factors.Add(i); n /= i; } } if (n > 2) { factors.Add(n); } return factors; } static void Main(string[] args) { ArgumentNullException.ThrowIfNull(args); while (true) { Console.Write("请输入第一个数："); int n1 = Convert.ToInt32(Console.ReadLine());//记录第一个数 Console.Write("请输入第二个数："); int n2 = Convert.ToInt32(Console.ReadLine());//记录第二个数 if (n1 * n2 != 0) //判断两个数中的一个是否为0 { Console.WriteLine("{0}和{1}的最小公倍数为{2}", n1, n2, LeastComMultiple(n1, n2));//输出最小公倍数 } else { Console.WriteLine("这两个数不能为0。"); } } } } } //运行结果： /* 请输入第一个数：12 请输入第二个数：18 12和18的最小公倍数为36 请输入第一个数：9 请输入第二个数：6 9和6的最小公倍数为18 请输入第一个数： */

        分解质因数法是一种求最小公倍数的算法，其基本思想是将两个数分解为质因数，然后取每个质因数的最高次幂相乘即可得到最小公倍数。在上述代码中，我们首先使用 GetPrimeFactors 函数将两个数分解为质因数，然后对这两个质因数列表进行排序，接着依次比较两个列表中的质因数，取每个质因数的最高次幂相乘，即可得到最小公倍数。