求解最大公约数的多种Way：
1 暴力解决法：M不断自减找到最大公约数。
2 辗转相除法：反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数。
3 更相减损术：若两者都为偶数，进行折半，直到一方奇数，再进行辗转相减。
一、什么是暴力解决法呢？
如果给定两个数：18、24，该如何求这两个数的最大公约数？接下来是最最最简单的方法。
我们仔细想一想，最大公约数有没有可能比18大呢？那么我们就可以找出两者中的最小值并假设最大公约数M就是为18，然后对18和24同时取模，发现两个不能同时整除。于是M不断自减，直到M=6的时候能同时整除18和24，此方法代码如下↓
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> int main() { int a = 0; int b = 0; //输入 scanf("%d %d",&a,&b); //找出最小值 int m = a > b ? b : a; //假设M为最大公约数 while (1) { if (a % m == 0 && b % m == 0) { break; } m--; } printf("%d\n",m); return 0; }
其中while（1）为真，恒成立
二、什么是辗转相除法呢？
是指用于计算两个非负整数a，b的最大公约数。计算公式gcd(a,b) = gcd(b,a mod b)。
假如需要求 1997 和 615 两个正整数的最大公约数,用辗转相除法，是这样进行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int main() { int a = 0; int b = 0; int m = 0; scanf("%d %d", &a, &b); while (m = a % b) { a = b; b = m; } printf("最大公约数：%d\n", b); return 0; }
这里会有疑问到：如果a的数大于b呢？我们可以验证一下
18 / 24 = 0 (余 18)
24 / 18 = 1(余6)
运算到这里我们就可以发现a和b的数自然而然的换了回来 公约数依然是6。
ps：两个数a、b的最大公倍数则是m，最小公倍数是（a*b/m）
三、什么是更相减损术呢？
例1：用更相减损术求98与63的最大公约数。（一奇一偶）
由于63不是偶数，把98和63以大数减小数，并辗转相减：
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
当差和被减数相等时候，运算结束
所以，98和63的最大公约数等于7。
例2、用更相减损术求260和104的最大公约数。（均为偶数）
解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。
此时65是奇数而26不是奇数，故把65和26辗转相减：
65-26=39
39-26=13
26-13=13（同理）
所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即1322=52。
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b); //都为偶数的情况 int n = 1; while ((a % 2 == 0) && (b % 2 == 0))//直到有一方不是偶数 跳出循环 { n *= 2; a = a / 2; b = b / 2; } while (1) { if (a < b)//交换，保证a>b { int temp = a; a = b; b = temp; } int sub = a - b; if (b == sub)//判断差和被减数是否相等，相等则跳出 break; else { a = b; b = sub; } } int sum = b* n; //最后的sum就是约掉的若干个2的积与b的乘积（当b=sub的时候） printf("最大公约数：%d\n", sum); return 0; }
如有错误，随时可以向我指出
