待到秋来九月八，我花开后百花杀

穷举法辗转相除法更相减损术 对于求最大公约数，有许多大数学家为此建立了许多不同的算法，在此我将对这些算法做一个总结和归纳。

穷举法

思路： 按从小到大（初值为1，最大值为两个整数当中较小的数）的顺序将所有满足条件的公约数列出，则按顺序，最后一个计算出的公约数即为最大公约数。

流程图：

Created with Raphaël 2.2.0 START Enter num1,num2 num1<num2 ? temp = num1; num1 = num2; num2 = temp; temp=0 i=0 i<num1 ? num1%i == 0 && num2%i == 0 ? temp=i i++ 输出temp，即为最大公约数 END yes no yes no yes no

程序代码：

//An highlighted blockvar foo = 'bar' #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<Windows.h> int main() { int num1, num2, temp, i; printf("please input number:\n"); scanf("%d %d", &num1, &num2); // if (num1 < num2) // { // temp = num1; // num1 = num2; // num2 = temp; // } temp = 0; for (i = 1; i < num1; i++) { if (num1%i == 0 && num2%i == 0) { temp = i; } } printf("the max common divisor : %d\n", temp); system("pause"); return 0; }

---

注意：因为是对两个数分别除以循环举例得到得数字，不存在因两个数得顺序不同会影响程序运行和结果的情况，可以省去交换步骤。

辗转相除法

思路： 又名欧几里德算法（Euclidean algorithm），用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

流程图：

Created with Raphaël 2.2.0 START Enter num1,num2 num1<num2 ? temp = num1; num1 = num2; num2 = temp; temp=0 temp=num1%num2 temp=0? 输出num2，即为最大公约数 END num1=num2 num2=temp yes no yes no

程序代码：

//An highlighted blockvar foo='bar' #include<stdio.h> #include<windows.h> #pragma warning(disable:4996) int main() { int num1, num2, temp; printf("please input number:\n"); scanf("%d %d", &num1, &num2); // if (num1 < num2) // { // temp = num1; // num1 = num2; // num2 = temp; // } temp = 0; while (1) { temp = num1 % num2; if (0 == temp) break; else { num1 = num2; num2 = temp; } } printf("the max common divisor : %d\n", num2); system("pause"); return 0; }

---

注意：辗转相除从理论上来说，两数字的前后顺序大小会对结果有影响，但对于计算机来说，取模运算如果前者比后者小，最后余为前者，那么传入下一次循环，会自动对两者进行交换，无需主动交换。

更相减损术

思路： 第一步：对于任意给定的两个正整数，判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

流程图：

Created with Raphaël 2.2.0 STAR Enter num1,num2,times=0,temp=0,i=0 num1%2==0 && num2%2==0 ? num1=num1÷2 num2=num2÷2 times++ num1<num2 ? i = num1; num1 = num2; num2 = i; temp=num1-num2 num1=temp temp==num2 ? 输出temp*2^(times)，即为最大公约数 END yes no yes no yes no

程序代码：

//An highlighted blockvar foo='bar' #include<stdio.h> #include<windows.h> #include<math.h> #pragma warning(disable:4996) int main() { int num1, num2, temp = 0, times = 0, i = 0; printf("please input number:\n"); scanf("%d %d", &num1, &num2); while(0 == num1 % 2 && 0 == num2 % 2) { num1 = num1 / 2; num2 = num2 / 2; times++; } while (1) { if (num1 < num2) { i = num1; num1 = num2; num2 = i; } temp = num1 - num2; num1 = temp; if (temp == num2) { printf("the max common divisor : %d\n", temp*(int)pow(2, times)); break; } } system("pause"); return 0; }