[已解决]c++

王鹿其

编程求一组整数的最大公因子和最小公倍数。

最佳答案

月排行榜 / 总排行榜

isdkz

2023-10-22 10:57:16

最大公因子（Greatest Common Divisor，简称GCD）是指能够同时整除两个或多个整数的最大正整数。最小公倍数（Least Common Multiple，简称LCM）是指能够同时被两个或多个整数整除的最小正整数。

在C++中，可以使用欧几里得算法来求取两个整数的最大公因子。以下是一个示例代码：

1. #include <iostream>
   
2. 
   
3. // 求最大公因子
   
4. int gcd(int a, int b) {
   
5.     while (b != 0) {
   
6.         int temp = a % b;
   
7.         a = b;
   
8.         b = temp;
   
9.     }
   
10.     return a;
    
11. }
    
12. 
    
13. // 求最小公倍数
    
14. int lcm(int a, int b) {
    
15.     return a * b / gcd(a, b);
    
16. }
    
17. 
    
18. int main() {
    
19.     int num1, num2;
    
20.     std::cout << "请输入两个整数: ";
    
21.     std::cin >> num1 >> num2;
    
22. 
    
23.     int gcdResult = gcd(num1, num2);
    
24.     int lcmResult = lcm(num1, num2);
    
25. 
    
26.     std::cout << "最大公因子: " << gcdResult << std::endl;
    
27.     std::cout << "最小公倍数: " << lcmResult << std::endl;
    
28. 
    
29.     return 0;
    
30. }
    

复制代码

这段代码首先定义了两个函数  gcd  和  lcm ，分别用于求取最大公因子和最小公倍数。在  gcd  函数中，使用了欧几里得算法来迭代求取最大公因子。在  lcm  函数中，直接利用最大公因子的概念来计算最小公倍数。

在主函数中，首先通过输入获取两个整数，然后分别调用  gcd  和  lcm  函数来计算最大公因子和最小公倍数，并将结果输出。

希望这个回答对你有帮助！如果你有任何其他问题，请随时提问。

跳转到最佳答案楼层

isdkz

最大公因子（Greatest Common Divisor，简称GCD）是指能够同时整除两个或多个整数的最大正整数。最小公倍数（Least Common Multiple，简称LCM）是指能够同时被两个或多个整数整除的最小正整数。

在C++中，可以使用欧几里得算法来求取两个整数的最大公因子。以下是一个示例代码：

1. #include <iostream>
   
2. 
   
3. // 求最大公因子
   
4. int gcd(int a, int b) {
   
5.     while (b != 0) {
   
6.         int temp = a % b;
   
7.         a = b;
   
8.         b = temp;
   
9.     }
   
10.     return a;
    
11. }
    
12. 
    
13. // 求最小公倍数
    
14. int lcm(int a, int b) {
    
15.     return a * b / gcd(a, b);
    
16. }
    
17. 
    
18. int main() {
    
19.     int num1, num2;
    
20.     std::cout << "请输入两个整数: ";
    
21.     std::cin >> num1 >> num2;
    
22. 
    
23.     int gcdResult = gcd(num1, num2);
    
24.     int lcmResult = lcm(num1, num2);
    
25. 
    
26.     std::cout << "最大公因子: " << gcdResult << std::endl;
    
27.     std::cout << "最小公倍数: " << lcmResult << std::endl;
    
28. 
    
29.     return 0;
    
30. }
    

复制代码

这段代码首先定义了两个函数  gcd  和  lcm ，分别用于求取最大公因子和最小公倍数。在  gcd  函数中，使用了欧几里得算法来迭代求取最大公因子。在  lcm  函数中，直接利用最大公因子的概念来计算最小公倍数。

在主函数中，首先通过输入获取两个整数，然后分别调用  gcd  和  lcm  函数来计算最大公因子和最小公倍数，并将结果输出。

希望这个回答对你有帮助！如果你有任何其他问题，请随时提问。

Mike_python小

问题描述：

给定两个整数 a 和 b，求它们的最大公因数和最小公倍数。


解决方案：

1、最大公因数可以使用辗转相除法求解，即：

2. int gcd(int a, int b) {
3.     if (a < b) {
4.         swap(a, b);
5.     }
6.     while (b != 0) {
7.         int r = a % b;
8.         a = b;
9.         b = r;
10.     }
11.     return a;
12. }

复制代码

在上述代码中，我们首先比较 a 和 b 的大小，确保 a >= b。然后使用 while 循环执行辗转相除法求最大公因数，最终返回结果。

2、最小公倍数可以通过最大公因数求出，即：a * b / gcd(a, b)。因此，我们可以在调用 gcd 函数后直接计算得到：

2. int lcm(int a, int b) {
3.     return a * b / gcd(a, b);
4. }

复制代码

结合上述两个函数，我们可以实现完整的程序：

2. #include <iostream>
3. using namespace std;
5. int gcd(int a, int b) {
6.     if (a < b) {
7.         swap(a, b);
8.     }
9.     while (b != 0) {
10.         int r = a % b;
11.         a = b;
12.         b = r;
13.     }
14.     return a;
15. }
17. int lcm(int a, int b) {
18.     return a * b / gcd(a, b);
19. }
21. int main() {
22.     int a, b;
23.     cin >> a >> b;
25.     int max_common_divisor = gcd(a, b);
26.     int min_common_multiple = lcm(a, b);
28.     cout << "最大公因数：" << max_common_divisor << endl;
29.     cout << "最小公倍数：" << min_common_multiple << endl;
31.     return 0;
32. }

复制代码

希望这能帮助到你！

球一个最佳答案谢谢啦！这对我非常重要！

陶远航

在C++中，我们可以使用欧几里得算法（Euclidean Algorithm）来找到两个数的最大公因数（GCD），然后使用这个GCD来找到这两个数的最小公倍数（LCM）。以下是一个简单的C++程序，它可以找到一组整数的最大公因数和最小公倍数：

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. // Function to find gcd of a and b
   
6. int gcd(int a, int b) {
   
7.     if (b == 0)
   
8.         return a;
   
9.     return gcd(b, a % b);
   
10. }
    
11. 
    
12. // Function to find lcm of a and b
    
13. int lcm(int a, int b) {
    
14.     return (a / gcd(a, b)) * b;
    
15. }
    
16. 
    
17. // Function to find gcd and lcm of a vector of numbers
    
18. pair<int, int> findGCDAndLCM(vector<int> numbers) {
    
19.     int n = numbers.size();
    
20.     int resultGCD = numbers[0];
    
21.     int resultLCM = numbers[0];
    
22. 
    
23.     for (int i = 1; i < n; i++) {
    
24.         resultGCD = gcd(numbers[ i], resultGCD);
    
25.         resultLCM = lcm(resultLCM, numbers[ i]);
    
26.     }
    
27. 
    
28.     return make_pair(resultGCD, resultLCM);
    
29. }
    
30. 
    
31. int main() {
    
32.     vector<int> numbers = {2, 7, 3, 9, 4};
    
33.     pair<int, int> result = findGCDAndLCM(numbers);
    
34. 
    
35.     cout << "GCD: " << result.first << endl;
    
36.     cout << "LCM: " << result.second << endl;
    
37. 
    
38.     return 0;
    
39. }
    

复制代码

这个程序首先定义了两个函数，一个用于计算两个数的最大公因数，另一个用于计算两个数的最小公倍数。然后，它定义了一个函数，该函数接受一个整数向量，并使用前面定义的函数来找到这个向量中所有数的最大公因数和最小公倍数。最后，主函数创建了一个整数向量，调用了findGCDAndLCM函数，并打印出结果。

请注意，这个程序假设输入的整数向量至少包含一个元素，并且所有的元素都是正整数。如果这些假设不成立，你可能需要对程序进行一些修改。
请注意，本回答来自GPT-4
如果问题已经解决，请设置最佳答案

柿子饼同学

1. int gcd(int a, int b){
   
2.     if(!b) return a;
   
3.     return gcd(b, a % b);
   
4. }
   
5. 
   
6. int lcm(int a, int b){
   
7.     return a*b / gcd(a, b);
   
8. }

复制代码