2. 计算最大公约数

给出两个数x和y，其最大公约数（或缩写为GCD）是能够同时被两个数整除的最大数。

假设任务是写一个函数，该函数将整型数x和y作为输入，返回它们的GCD。 那么，该函数的原型为：

int GCD(int x, int y);

利用最基本的测试算法，这个问题存在几个可用的解决方案。

2.1 brute-force算法

计算GCD的最简单的方法基于最通用的方法，称为brute-force方法(brute-force method)。

该方法测试每一种可能性。

代码实现如下：

#include <stdio.h> #include <stdbool.h> /* Calculate the greatest common divisor. */ /* Function Prototype */ int GCD(int x, int y); /* Main Program */ main() { int x, y; printf("Input first positive integer: "); scanf("%d", &x); printf("Input second positive integer: "); scanf("%d", &y); printf("GCD between %d and %d is: %d\n", x, y, GCD(x, y)); } /* Function */ int GCD(int x, int y) { int g; g = x; while (x % g != 0 || y % g !=0) { g--; } return g; }

2.2 欧几里德算法

欧几里德算法描述如下： (1) 取x除以y的余数，称余数为r。 (2) 如果r是0，过程完成，答案是y。 (3) 如果r非0，设x等于原来y的值，y等于r，重复整个过程。

代码实现

方法一：

/* Function */ int GCD(int x, int y) { int r; while (true) { r = x % y; if (r != 0) { x = y; y = r; } else {return y;} } }

方法二：

int GCD(int x, int y) { int r; while (true) { r = x % y; if (r == 0) break; x = y; y = r; } return y; }

2.3 欧几里德算法的正确性说明

通过希腊人所用的数学思想模型给出这个证明的概述。

在希腊数学中，几何学占据了中心位置，数字被认为是距离。

当找两个数（如55和15）的最大公约数时，可将这个问题设想成找出一根最大的用于测量这两个距离的木棍，该木棍能用来划分两个距离中每一个距离。

因此，可以把这个问题想象为两根木棍，一根55单位长，另一根是15单位长，如下图所示：

该问题是要找到一个新的测量木棍，以该木棍为单位可以均分两根木棍x和y。

欧几里德算法从用较短的一个距离作为单位来划分长的木棍开始：

在这个例子中，以15为单位可以将55分为三份，但还余10，这意味着阴影部分是10个单位长。

欧几里德最基本的想法是，原先两个距离的最大公约数也必须是较短的木棍的长度和图中阴影部分表示的距离的最大公约数。

由此，解决原先的问题可简化为涉及两个较小数的更简单的问题。

这里，两个新的数是15和10，可以从把两个新值x’和y’作为合适的测量长度着手。然后用较小的一个长度划分较长的长度。

这个过程再一次产生了一段剩余的区域，这次长度为5。

如果再重复一次这个过程，会发现长度为5的阴影部分本身就是x’和y’的公约数，因此，也是原先两个数x和y的公因子。

如下图所示：

参考 《C语言的科学和艺术》 —— 第6章 算法