题解 | #最大公约数#

1.穷举法：从两个数中更小的那一个数开始循环（递减）至1，寻找最大公约数。 很遗憾，此法超时。具体代码见下：

#include<stdio.h>
int main() {
	int A, B, min, i;
	scanf("%d %d", &A, &B);
	min = (A <= B) ? A : B;
	for (i = min; i >= 2; i--) {
		if (A % i == 0 && B % i == 0)
			break;
	}
	printf("%d\n", i);
	return 0;
}//此法超时

2.辗转相除法：用较大数A除以较小数B，再将余数值赋给B，将B值赋给A......如此反复，直到最后余数是0为止。最后的除数(即最终A的值)就是所求的最大公约数。 代码见下：

int main() {
	int A, B, temp;
	scanf("%d %d", &A, &B);
	if (A < B) { //若A<B则交换A,B的值，使A表示两数中更大的那个数
		temp = A;
		A = B;
		B = temp;
	}
	while (B != 0) { //辗转相除法
		temp = A % B;
		A = B;
		B = temp;
	}
	printf("%d\n", A);
	return 0;
}