欧几里德算法

2018-02-16 184 words One minute views

欧几里德算法是用来求两个正整数最大公约数的算法。是由古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里德算法。

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。

1
2
3
4
5
6
7
8
9


/**
 * 欧几里德算法
 */
public static int gcd(int p, int q) {
  if (q == 0) {
    return p;
  }
  return gcd(q, p % q);
}