给定两个数，求这两个数的最大公约数

最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。求解的方式比较多，暴力穷举、辗转相除法、更相减损法、Stein算法。
1.暴力穷举法
如果大数可以整除小数，那么最大公约数为小数。如果不能整除小数，那么这两个数就按大到小依次对比小数小的数求余，遇到都能够整除的，就是最大公约数。

#include<stdio.h>
#include<windows.h>
#pragma warning(disable:4996)
int main(){
	//暴力穷举法
	int a = 0;
	int b = 0;
	printf("请输入两个整数:");
	scanf("%d%d", &a, &b);
	if (a >= b){
		int i = 0;
		for (i = b; i >= 1; i--){
			if (a%i == 0 && b%i == 0){
				printf("最大公约数为：%d\n", i);
				break;
			}
		}
	}
	else{
		int j = 0;
		for (j = a; j >= 1; j--){
			if (a%j == 0 && b%j == 0){
				printf("最大公约数为：%d\n", j);
				break;
			}
		}
	}
	system("pause");
	return 0;
}

2.辗转相除法
用大数对小数求余，若余数为0，则除数为最大公约数。若余数不为0，将此余数作为除数，小数作为被除数，重新求余，直到余数为0为止。此时的最大公约数为余数。

#include<stdio.h>
#include<windows.h>
#pragma warning(disable:4996)
int main(){
	int a = 0;
	int b = 0;
	printf("请输入两个整数:");
	scanf("%d%d", &a, &b);
	if (a >= b){
		int c = a%b;
		while (c != 0){
			a = b;
			b = c;
			c = a%b;
		}
		printf("最大公约数为：%d\n",b);
	}
	else{
		int d = b%a;
		while (d != 0){
			b = a;
			a = d;
			d = b%a;
		}
		printf("最大公约数为：%d\n", a);
	}
	system("pause");
	return 0;
}

3.更相减损法
当两个数相等时，最大公约数为他们其中任意一个；当两个数不相等时，用大数减小数得到的差和之前的那个小数再次相减，直到两个数相等，相等的两个中，任意一个都是最大公约数。

#include<stdio.h>
#include<windows.h>
#pragma warning(disable:4996)
int main(){
	//更相减损法
	int a = 0;
	int b = 0;
	printf("请输出两个整数:");
	scanf("%d%d", &a, &b);
	while ((a - b)!=0){
		if (a > b){
			a = a - b;
		}
		else{
			b = b - a;
		}
	}
	printf("最大公约数为：%d\n", b);
	system("pause");
	return 0;
}

4.Stein算法
步骤：
step1：两数均为偶数时将其同时除以2至至少一数为奇数为止，记录除掉的所有公因数2的乘积k；
step2：如果仍有一数为偶数，连续除以2直至该数为奇数为止；
step3：用更相减损法(辗转相减法)，即GCD(a,b)=GCD(a-b,b)，或辗转相除法求出两奇数的最大公约数d；
step4：原来两数的最大公约数即为d*k。

#include<stdio.h>
#include<windows.h>
#pragma warning(disable:4996)
int main(){
	//Stein算法
	int a = 0;
	int b = 0;
	printf("请输入两个整数:");
	scanf("%d%d", &a, &b);
	int gcd = 0;
	int k = 1;
	while ((!(a & 1)) && (!(b & 1))){       //step1;
		k <<= 1;                            //用k记录全部公因子2的乘积 ；
		a >>= 1;
		b >>= 1;
	}
	while (!(a & 1))a >>= 1;                //step2;
	while (!(b & 1))b >>= 1;
	if (a<b) a ^= b, b ^= a, a ^= b;        //交换，使a为较大数； 
	while (a != b){                         //step3;
		a -= b;
		if (a<b) a ^= b, b ^= a, a ^= b;
	}
	gcd = k*a;
	printf("最大公约数为：%d\n", gcd);
	system("pause");
	return 0;
}