本文主要向大家介绍了如何用C语言求两个数的最大公约数的三种算法，通过具体的实例让大家了解，希望对大家学习C语言有所帮助。

最大公约数：指某几个整数共有约数中最大的一个。

方法一:相减法 也叫更相减损法

思路：

1.如果a>b  a = a - b;

2.如果b>a    b = b - a;

3.假如a = b ，则 a或b  是最大公约数

4.如果a != b,则继续从1开始执行

5.也就是说循环的判断条件为a != b  ，直到a = b时，循环结束。

举例说明：

a = 28 b = 21

a>b    

则  a = a - b = 28 - 21 = 7

      b = 21    

b>a

则  b = b-a = 21 - 7 = 14

              a = 7

b>a 

则 b = b - a = 14 - 7 = 7

             a = 7

此时 a = b =7

循环结束

代码展示：

[cpp] view plain copy print?
1. #include <stdio.h>  
2. int main()  
3. {  
4.     int a,b;  
5.     printf("输入两个数字求最大公约数：");  
6.     scanf("%d%d",&a,&b);  
7.     while(a != b)  
8.     {  
9.         if(a > b)  
10.             a = a - b;  
11.         else  
12.             b = b - a;  
13.     }  
14.     printf("最大公约数为：%d\n",a);  
15.   
16.     return 0;  
17.   
18. }

运行效果：

方法二：穷举法

思路：

1.选出a，b中最小的一个数字放到c中

2.分别用a，b对c求余数，即看是否能被c整除

3.直到a，b同时都能被c整除

4.如不能整除，c-- (c的值减一) 继续从2开始执行

5.也就是说该循环的判断条件为 a，b能否同时被c整除，只要有一个数不能被c整除，循环继续执行

举例说明： 

a = 9 b = 4

将其中最小的数字赋予c

c = 4

a%c = 1 ,b%c = 0  a,b不能同时被c整除 循环继续

c-- ，c = 3

a%c = 0 ,b%c = 1  a,b不能同时被c整除 循环继续

c-- ，c = 2

a%c = 1 ,b%c = 0  a,b不能同时被c整除 循环继续

c-- ，c = 1

a%c = 0 ,b%c = 0  a,b同时被c整除  循环结束 c是a和b的最大公约数

代码展示：

[cpp] view plain copy print?
1. #include<stdio.h>    
2. int main()  
3. {  
4.       
5.     int a,b,c;  
6.     printf("输入两个数字求最大公约数：");  
7.     scanf("%d%d",&a,&b);  
8.     c=(a>b)?b:a;   //三目运算符 将最小的赋给c  
9.     while(a%c!=0||b%c!=0)    //a，b同时能被c整除 不执行该循环  
10.     {  
11.         c--;  
12.     }  
13.     printf("最大公约数为：%d\n",c);  
14.       
15. }

三目运算符

运行效果：

方法三：辗转相除法

思路：

1.将两整数求余 a%b = c

2.如果c = 0;则b为最大公约数 

3.如果c != 0,则 a = b；b = c；继续从1开始执行

4.也就是说该循环的是否继续的判断条件就是c是否为0

举例说明：

a = 21    b = 28

c = a%b = 21%28 = 21， 则c = 21  此时c不为0

执行    a = b ，   b = c   ，   a = 28 ，b = 21

c = a%b = 28%21 = 7   ，则c = 7    此时c不为0

执行    a = b ，   b = c   ，   a = 21 ,  b = 7

c = a%b = 21%47 = 0   ，则c = 0 循环结束

代码展示：

[cpp] view plain copy print?
1. # include <stdio.h>  
2. int main ()  
3. {  
4.     int a,b,c;  
5.     while(1)  
6.     {  
7.         printf("输入两个数字求最大公约数：");  
8.         scanf("%d%d",&a,&b);  
9.         c = a%b;  
10.         while(c!=0)  
11.         {  
12.             a = b;  
13.             b = c;  
14.             c = a%b;  
15.         }  
16.         printf("最大公约数为：%d\n",b);  
17.     }  
18. }

运行效果：

以上就介绍了C/C+的相关知识，希望对C/C+有兴趣的朋友有所帮助。了解更多内容，请关注职坐标编程语言C/C+频道！