作者：解学武

求任意两个正整数的最大公约数（GCD）。

分析

如果有一个自然数 a 能被自然数 b 整除，则称 a 为 b 的倍数，b 为 a 的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。

根据约数的定义可知，某个数的所有约数必不大于这个数本身，几个自然数的最大公约数必不大于其中任何一个数。要求任意两个正整数的最大公约数即求出一个不大于其中两者中的任何一个，但又能同时整除两个整数的最大自然数。

实现

思路有两种：第一种，采用穷举法按从小到大（初值为 1，最大值为两个整数当中较小的数）的顺序将所有满足条件的公约数列出，输出其中最大的一个；第二种，按照从大（两个整数中较小的数）到小（到最小的整数 1）的顺序求出第一个能同时整除两个整数的自然数，即为所求。

下面对第二种思路进行详细说明。

两个数的最大公约数有可能是其中的小数，所以在按从大到小顺序找寻最大公约数时，循环变量i的初值从小数 n 开始依次递减，去寻找第一个能同时整除两整数的自然数，并将其输出。需要注意的是，虽然判定条件是 i>0，但在找到第一个满足条件的i值后，循环没必要继续下去，如，25 和 15，最大公约数是 5，对于后面的 4、3、2、1 没必要再去执行，但此时判定条件仍然成立，要结束循环只能借助 break 语句。

下面是完整的代码：

#include<stdio.h>
int main()
{
    int m, n, temp, i;
    printf("输入两个数:");
    scanf("%d%d", &m, &n);
    if (m < n)  /*比较大小，使得m中存储大数，n中存储小数*/
    { /*交换m和n的值*/
        temp = m;
        m = n;
        n = temp;
    }
    for (i = n; i > 0; i--)  /*按照从大到小的顺序寻找满足条件的自然数*/
        if (m % i == 0 && n % i == 0)
        {/*输出满足条件的自然数并结束循环*/
            printf("%d和%d的最大公约数为: %d\n", m, n, i);
            break;
        }

    return 0;
}

运行结果：

输入两个数:100 125
125和100的最大公约数为: 25

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。