GCD算法的迭代版本

《数论与代数的计算性导论》 华南师范大学 王立斌
欧几里德算法 (Euclidean algorithm)计算两个整数的最大公因子，也简记为 gcd 算法 。这是一种古老的、著名的，且目前依然应用广泛的算法，其历史可以追溯到古希腊数学家欧几里德 (Euclid)。
定理 2.1. 欧几里德算法
给定两个整数 a 和 b，设 a ≥ b，则 a 和 b 的最大公因子等于 b 和 a mod b 的最大公因子。即
gcd(a, b) = gcd(b, a mod b)
其中，a mod b 表示用 a 除以 b 所得到的余数 r。

gcd算法的Ｃ＋＋迭代版本
（使用visual　studio２０１９）

#include
using namespace std;
int main()
{
	int GCD(int a, int b);
	int a, b;
	cout << "请输入两个正整数n";
	cin >> a >> b;
	cout << "它们的最大公因数是：" << GCD(a, b);
	return 0;
}
int GCD(int a, int b)
{
	int temp;
	if (b > a)
	{
		temp = a;
		a = b;
		b = temp;
	}
	while (b != 0)
	{
		temp = b;
		b = a % b;
		a = temp;
	}
	return a;
}

（由于理论上负数没有最大公因数，因此这里规定ａ和ｂ全部为正整数）
测试：