求两个数的最大公约数

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

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

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;
}