HiSEN

常见算法：Java求最小公倍数和最大公约数三种算法

发表于 | 分类于

最小公倍数：
数论中的一种概念，两个整数公有的倍数成为他们的公倍数

其中一个最小的公倍数是他们的最小公倍数

同样地，若干个整数公有的倍数中最小的正整数称为它们的最小公倍数

求最小公倍数算法：

最小公倍数=两整数的乘积÷最大公约数

求最大公约数算法：

(1) 辗转相除法

有两整数a和b：

  1. a%b得余数c
  2. 若c=0，则b即为两数的最大公约数
  3. 若c≠0，则a=b，b=c，再回去执行1

例如:求27和15的最大公约数过程为

  1. 27÷15余12
  2. 5÷12余3
  3. 12÷3余0

因此，3即为最大公约数

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * 最大公约数
 */
public int getGCD(int m, int n) {
  if (n == 0) {
    return m;
  }
  return getGCD(n, m % n);
}

/**
 * 最小公倍数
 * @param m
 * @param n
 * @return
 */
public int getLCM(int m, int n) {
  int mn = m * n;
  return mn / getGCD(m, n);
}

/**
   * 辗转相除求最大公约数
   * 有两整数a和b：
   * ① a%b得余数c
   * ② 若c=0，则b即为两数的最大公约数
   * ③ 若c≠0，则a=b，b=c，再回去执行①
   */
  public int divisionGCD(int m, int n) {
    int a;
    while (n != 0) {
      a = m % n;
      m = n;
      n = a;
    }
    return m;
  }
  /**
   * 相减法求最大公约数
   * 有两整数a和b：
   * ① 若a>b，则a=a-b
   * ② 若a<b，则b=b-a
   * ③ 若a=b，则a（或b）即为两数的最大公约数
   * ④ 若a≠b，则再回去执行①
   */
  public int subtractionGCD(int m,int n){
    while(m != n){
      if (m>n){
        m = m-n;
      }else {
        n = n - m;
      }
    }
    return m;
  }