如何快速找到两个数的最大公约数？

本文共计607个文字，预计阅读时间需要3分钟。

求最大公约数有两种方法：更相减损法，辗转相除法。两种方法原理相同，辗转相除法更简洁。1. 更相减损法：假设有两个数161和63，设它们的最大公约数为x，则x能整除161和63。它们的差为161-63=98，也能被x整除。所以，它们的最大公约数x也能整除98。继续这个过程，直到两个数相等，那个数就是它们的最大公约数。2. 辗转相除法：用161除以63，得到商2余35，再用63除以35，得到商1余28，以此类推，直到余数为0，最后的除数就是最大公约数。

求最大公约数有两种方法：更相减损法，辗转相除法

两种方法原理相同，辗转相除法更简洁

1.更相减损法

假设有两个数161和63，设它们的最大公约数为x

161和63都能被x整除，则它们的差161－63=98也能被x整除，所以求161和63的最大公约数变成求98和63的最大公约数，且98和63的最大公约数仍然是x。

98和63都能被x整除，则它们的差98－63=35也能被x整除,所以求98和63的最大公约数变成求63和35的最大公约数，且63和35的最大公约数仍然是x。

同理 63－35=28 求28和35的最大公约数

35－28=7 求28和7的最大公约数

28－7=21 求21和7的最大公约数

21－7=14 求14和7的最大公约数

14－7=7 求7和7的最大公约数，即x=7

直到两个数相同，最大公约数即为其本身。

代码实现

#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> //gcd(greateest commom divisor) 最大公约数 int get_gcd(int x, int y) { int z = 0; while (1) { if (x > y) { z = x - y; x = y; y = z; } else if (x < y) { z = y - x; y = x; x = z; } else return x; //此处return直接终止函数，while循环的break可以省略 } } int main() { int a = 0; int b = 0; scanf("%d%d", &a, &b); int gcd = get_gcd(a, b); printf("%d", gcd); return 0; }

2.辗转相除法

同样假设有两个数161和63，设它们的最大公约数为x

161/63=2余35

63/35=1余28

35/ 28=1余7

28/7=4余0（余0代表可以整除）

所以x=7

代码实现

#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> int get_gcd(int x, int y) { int z = 1; if (x > y) { while (z!=0) { z = x % y; x = y; y = z; } return x; } else if (x < y) { while (z != 0) { z = y % x; y = x; x = z; } return y; } else return x; } int main() { int a = 0; int b = 0; scanf("%d%d", &a, &b); int gcd = get_gcd(a, b); printf("%d", gcd); return 0; }