leeyupeng

leeyupeng@126.com

0%

最大公约数,最小公倍数

发表于 更新于 分类于 阅读次数： Valine：

最大公约数

欧几里得算法(辗转相除法)

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。
计算公式gcd(a,b) = gcd(b,a mod b)。 

1
2
3
4
5
6
int gcd(int a，int b)
{
    if (a < b)
        std::swap(a, b);
    return b == 0 ? a : gcd(b, a % b);
}

Stein算法

Stein算法由J. Stein于1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。

gcd(a,a) = a，也就是一个数和他自身的公约数是其自身
gcd(ka,kb) = k gcd(a,b），也就是最大公约数运算和倍乘运算可以交换，特殊的,当k=2时，说明两个偶数的最大公约数必然能被2整除 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int gcd_stein(int a, int b) {
  if (a < b)
    std::swap(a, b);

  if (b == 0) {
    return a;
  }
  else if ((a & 0x01) == 0 && (b & 0x01) == 0) {
    return gcd_stein(a >> 1, b >> 1)<<1;
  }
  else if ((a & 0x01) == 0)
  {
    return gcd_stein(a >> 1,b);
  }
  else if ((b & 0x01) == 0)
  {
    return gcd_stein(a, b >> 1);
  }
  else
  {
    return gcd_stein((a - b) >> 1, b);
  }
}

最小公倍数

通过最大公约数求最小公倍数

公式 a*b/gcd(a,b)

分解质因数法

先把这几个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积（如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）。