欧几里得算法

介绍

欧几里德算法，又叫做辗转相除法，用于计算两个正整数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++版本

#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函数

import math
a=int(input())
b=int(input())
#输出最大公约数
print(math.gcd(a,b))

1. 手写GCD

#自定义函数
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))