欧几里得算法

介绍

欧几里德算法,又叫做辗转相除法,用于计算两个正整数a,b的最大公约数(the greatest common divisor)。

计算公式

$$
gcd(a,b)=gcd(b,a\mod b)
$$

证明

第一步:不妨假设 $c=gcd(a,b)$,则 $a=mc$,$b=nc$,其中 $m,n∈z$

第二步:取 $r=a-kb=(m-nk)c$ ,其中$k∈z$,易得 $c$ 也是 $r$ 的因子

第三步:而 $r \mod b=(a-kb)\mod b=a \mod b$,即 c 也是 a mod b 的一个因子

从而 $c = gcd(a,b) = gcd(b,a \mod b)$,结论得证

代码

C++版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
//定义函数
int my_gcd(int a,int b)
{
while (a%b!=0)
{
int c=a;
a=b;
b=c%b;
}
return b;
}
//主程序
int main()
{
int a,b;
std::cin>>a>>b;
std::cout<<my_gcd(a,b)<<std::endl;
return 0;
}

除此之外,还可以用递归来定义此函数

python版本

  1. 使用math库中带的gcd函数
1
2
3
4
5
import math
a=int(input())
b=int(input())
#输出最大公约数
print(math.gcd(a,b))
  1. 手写GCD
1
2
3
4
5
6
7
8
9
10
11
#自定义函数
def my_gcd(a,b):
while a%b!=0:
c=a
a=b
b=c%b
return b

a=int(input())
b=int(input())
print(my_gcd(a,b))

欧几里得算法
https://serendipity565.github.io/posts/ba3cf0836f20/
作者
Serendipity
发布于
2023年11月18日
许可协议
BY-SERENDIPITY565