求两个正整数的最大公约数

解法一：根据定义，a与b的最大公约数是指能同时整除a与b的最大整数：

#include <stdio.h>
int main()
{
int num1 = 18;
int num2 = 26;
int com = 0;
printf("num1 = %d ; num2 = %d \n",num1,num2);
if( num1 >= num2)
{
    com = num2;
}
else
{
    com = num1;
}
for(com; com > 0; com--)
{
    if((num1 % com == 0 && num2 % com == 0) || com == 1 )
    {
        printf("最大公约数为: %d \n",com);
        break;
    }
}
    return 0;
}

这种是通过定义来设计的程序，应该是最容易让人接受的一种，下面两种就有一点难理解了。

解法二：我够古代数学家对公约数求解问题进行可研究并提出了算法，称之为更相减损之术，其方法是以两数中较大的数减去较小的数，获得的差与原先较小的数构成新的一对数，再以大的数减去小的数，依次循环，同样的方法操作，直至产生一对相等的数为止。该数即为最大公约数。例如，求12,16折两个数的最大公约数，具体操作如下：

（12,16）？（12,4）？（8,4）？（4,4）可见，4是12和16的最大公约数。

程序如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int Com_divisor(int n,int m)
{
    int div = n;
while(div>1)
{
         if(n<m)
{
        div = m - n;
if(div == n)
{
    return div;
}
else 
{
m = div;
}
}
else
{
        div = n - m;
if(div == m)
{
    return div;
}
else 
{
n = div;
}
}
}

}

int main()
{
int n = 12;
int m = 16;
printf("n = %d ; m = %d \n",n,m);
printf("最大公约数为：%d \n",Com_divisor(n,m));
    return 0;
}

程序结果也是如此：

解法三：古希腊数学家也对公约数求解问题研究提出的算法称为辗转相除法（见欧几里的算法）。具体的方法是用较大的数除以较小的数，余数和较小的数构成新的一对数，继续上面的除法，知道大数被小数出尽为止，则较小的数就是最大公约数。例如：求288和123的最大公约数，具体操作如下：

（288,123）->（42,123）->（42,39）->（3,39）可见3是288和123的最大公约数：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int Com_divisor1(int n, int m)
{
   int div =1;
   while(div)
   {
       if(n<m)
       {
            n = n ^ m;
    m = n ^ m;
    n = m ^ n;
       }
   div = n%m;
   n = div;
   if(div == 0)
   {
       return m;
   }
   }
}

int main()
{
int num1 = 288;
int num2 = 123;
printf("num1 = %d ; num2 = %d \n",num1,num2);
printf("最大公约数为：%d \n",Com_divisor1(num1,num2));
        return 0;
}

程序结果如此：

能力有限，有不对的地方欢迎指正。

内容有借鉴于《C语言程序设计基础》。