C++求最大公因数（两个数字版）

高山

前言
本帖将会告诉你C++如何做求解最大公因数（也叫最大公倍数）。
回复奖励1鱼币，3次（定时提升）

代码说明

自定义函数版

1. #include <bits/stdc++.h>//头文件
   
2. using namespace std;//命名空间
   
3. int gcd(int a,int b)//自定义函数求解
   
4. {
   
5.         if (a % b == 0)
   
6.         {
   
7.                 return b;
   
8.         }
   
9.         else
   
10.         {
    
11.                 return gcd(b,a % b);
    
12.         }
    
13. }
    
14. int main()
    
15. {
    
16.         int a,b;//定义
    
17.         cin >> a >> b;//输入
    
18.         cout << gcd (a,b);//输出
    
19.         return 0;
    
20. }
    

复制代码

C++自带函数版

1. #include<iostream>
   
2. #include<algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. int main()
   
7. {
   
8.         int n,m;
   
9.         cin >> n >> m;
   
10.         cout<< __gcd(n,m);
    
11. 
    
12.         return 0;
    
13. }

复制代码

附件下载（不用下C++也能用）

C++自带函数款
C 最大公因数（自带函数）.zip (431.88 KB, 下载次数: 2, 售价: 1 鱼币)

2022-8-21 11:10 上传

点击文件名下载附件
使用C++定义好的函数文件

C++自定义函数款（权限限制，先用腾讯微云，登录QQ账户即可）
https://share.weiyun.com/NlgrTJEg

额外减小

高山 发表于 2022-8-22 09:23
能说说吗

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.         int a,b,mid_result,min,n=2,s;
   
6.         printf("\n\
   
7.         求最大公约数与最小公倍数程序\n\n\
   
8.         请输入2个大于1的正整数（中间有空格）：\n");
   
9.         scanf("%d %d",&a,&b);
   
10.         printf("若要求最大公约数，请输入0，若要求最小公倍数，请输入1.\n");
    
11.         scanf("%d",&s);
    
12.         mid_result=a*b;
    
13.         if(a>=b)
    
14.         {
    
15.                 min=b;
    
16.         }
    
17.         else
    
18.         {
    
19.                 min=a;
    
20.         }
    
21.         while(n<=min)
    
22.         {
    
23.                 if((mid_result/n)%a||(mid_result/n)%b)
    
24.                 {
    
25.                         n++;
    
26.                 }
    
27.                 else
    
28.                 {
    
29.                         mid_result=mid_result/n;
    
30.                 }
    
31.         }
    
32.         if(s==0)
    
33.         {
    
34.                 printf(" %d 与 %d 的最大公约数为 %d !",a,b,a*b/mid_result);
    
35.         }
    
36.         else
    
37.         {
    
38.                 printf(" %d 与 %d 的最小公倍数为 %d !",a,b,mid_result);
    
39.         }
    
40.        
    
41.         return 0;
    
42. }

复制代码

以前随便做的冗长代码

一点点儿

支持楼主

dolly_yos2

反对楼主，希望楼主不要误人子弟。
从第一句“ C++如何做求解最大公因数（也叫最大公倍数）”就开始令人迷惑，试问楼主什么叫“最大公倍数”，又是怎么“也称最大公因数”的？
自定义函数和自带函数版具有相同的问题：不使用标准写法。头文件 bits/stdc++.h 和 __gcd 均没有在标准中被定义，在大多数情况下使用此类非标准内容都是强烈不推荐的——除非能够保证使用的功能将在应用的时间和空间范围之内保持稳定。
如果您想使用 C++ 内置的最大公因数计算函数，定义在头文件 <numeric> 中的 std::gcd 是一个不错（远比 __gcd 好得多）的选择。

额外减小

我有一种非常复杂的方法

高山

额外减小 发表于 2022-8-21 23:25
我有一种非常复杂的方法

能说说吗

陈尚涵

但是我请楼主先认识最大公因数和最大公倍数概念的定义
最大公因数：指两个数字共有的因数中最大的因数
最大公倍数：指两个数字都是他的因数且是符合条件中最大的，既无限，一般称之为最小公倍数
也就是说最大公因数≠最大公倍数
求最大公因数有很多方法，如辗转相减法，辗转相除法，还有穷举等
另外，最小公倍数=最大公因数×第一个数×第二个数

dolly_yos2

陈尚涵 发表于 2022-8-22 16:03
但是我请楼主先认识最大公因数和最大公倍数概念的定义
最大公因数：指两个数字共有的因数中最大的因数
...

又来捉虫了，「最小公倍数=最大公因数×第一个数×第二个数」不总是成立，仅当两个数互质时成立。您可能想描述的是「最小公倍数×最大公因数=第一个数×第二个数」

陈尚涵

dolly_yos2 发表于 2022-8-22 21:12
又来捉虫了，「最小公倍数=最大公因数×第一个数×第二个数」不总是成立，仅当两个数互质时成立。您可能 ...

对不起哈乘除反了

zhangjinxuan

一个错别字：前言那里，没有最大公倍数，应该是最大公约数