Ec673d55941ba51e8251ff8e248a5927
欧几里得算法

1 基础概念

  最大公约数:最大公约数,也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个。例如:18与12的最大公约数为6。20与36的最大公约数为4。

2 算法思想

  欧几里德算法又称辗转相除法,是指用于计算两个正整数m,n的最大公约数。计算公式为:
  gcd(m,n) = gcd(n,m mod n)。
其中,mod运算为取余运算。

例如:求18与12的最大公约数:

gcd(18,12)
= gcd(12, 18%12)
= gcd(12, 6)
= gcd(6, 12%6)
= gcd(6,0)
= 6

求20与36的最大公约数:

gcd(20,36)
= gcd(36, 20%36)
= gcd(36, 20)
= gcd(20, 36+)
= gcd(20, 16)
= gcd(16, 20%16)
= gcd(16, 4)
= gcd(4, 16%4)
= gcd(4, 0)
= 4

3 算法流程

4 代码实现

迭代方式:

int gcd(int m,int n)
{
    int r;
    while(n != 0)
    {
        int r = n;
        n = m%n;
        m = r;
    }
    return m;
}

递归方式:

```

int gcd(int m,int n)
{
if(n == 0)
{
return m;
}
return gcd(n, m%n);

top Created with Sketch.