本文共 735 字，大约阅读时间需要 2 分钟。

思路一：给定a，b两个数，将较小的数赋值给c，令c=b（不妨设a>b），将a和b对c做求余运算，从c开始依次减1向下遍历，直到两者的余数都为0则返回c，否则继续循环遍历。

代码如下：

#include
   
    int gcd(int a,int b){	int c;	c=(a>b)?b:a;	while(a%c!=0||b%c!=0)	{	c--;	}	return c;}int main(){	int a,b,max_div;	cout<<"please input two integer:";	cin>>a>>b;	max_div=gcd(a,b);	cout<<"the greatest common divisor of ";	cout<
    <<" and "<<<" is "<
      
       <
      
   

假设a>b,如果a不能被b整除，则将b赋值给a，余数赋值给b，重复执行a%b,直到a能够被b整除。此时返回b的值，则为最大公约数。

代码如下：

#include
   
    int gcd2(int a,int b){	int c;	if(a
    
     >a>>b;	max_div=gcd2(a,b);	cout<<"the greatest common divisor of ";	cout<
     <<" and "<<<" is "<
       
        <
       
    
   

很显然：方法2比方法1更加高效，优先推荐使用方法2

参考文献：http://blog.csdn.net/a1414345/article/details/51770430