最近发现了这样一种求最大公约数的算法，因此写此篇博客记录一下

欧几里得算法

欧几里德算法，也称为辗转相除法，是一种用于计算两个整数的最大公约数（GCD，Greatest Common Divisor）的经典算法。这个算法的名字来源于古希腊数学家欧几里德（Euclid），他在公元前300年左右的《几何原本》一书中首次描述了这一算法。

欧几里德算法的核心思想是通过不断取两个整数的余数，将问题规模不断减小，直到找到它们的公约数。算法的步骤如下：

  1. 假设有两个整数 a 和 b，其中 a > b。

  2. 计算 a 除以 b 的余数，记为 r（r = a % b）。

  3. 如果 r 等于 0，则 b 即为最大公约数，算法结束。否则，将 a 的值更新为 b，将 b 的值更新为 r，然后回到步骤 2。

  4. 重复步骤 2 和 3 直到余数 r 等于 0。此时，b 的值即为最大公约数。

欧几里德算法的关键观察是，两个整数的最大公约数等于其中较小的整数和这两个整数相除的余数的最大公约数。这个观察使得算法能够快速而有效地找到最大公约数，而且不需要枚举所有可能的因子。

欧几里德算法在计算机科学和数学领域中具有广泛的应用，包括：

  • 求解整数的最大公约数。
  • 判断两个整数是否互质（最大公约数为1）。
  • 求解不定方程的整数解，如贝祖等式。
  • 在密码学中用于生成加密密钥。

欧几里德算法是一种高效的算法，其时间复杂度是 O(log(min(a, b)))，其中 a 和 b 是输入的两个整数。这使得它成为解决大整数问题的首选方法。

代码实现如下：

1
2
3
4
5
6
int gcd(int a,int b){
	if(b==0){
		return a;
	}
	else return (b,a%b);
}