c++: 求最大公约数 与 最小公倍数

时间：2022-11-11 00:36:49

首先对于最大公约数，可以看下wiki上面的简介：

最大公约数（英语：Greatest Common Divisor，简写为G.C.D.；或Highest Common Factor，简写为H.C.F.），指某几个整数共有约数中最大的一个。
求两个整数最大公约数主要的方法：
列举法：各自列出约数，再找出最大的公约数。
素因数分解法：两数各作素因数分解，然后取出共有的项乘起来。
短除法
辗转相除法（扩展版）：常使用于直观上不容易判别公约数的场合。

我大致看了一下：

  • 列举法会比较笨，而且实现起来需要两个数组去存储对应的两个参数的公约数，然后需要比较两个数组中相同的数字，并且取出相同的数字中最大的那一个。这需要使用到数组，也就不得不涉及指针与引用的知识了。然而，对于c中的指针，我真的已经忘记得差不多了，于是就放弃了这种实现方式
  • 素因数分解法似乎无法使用程序去表达，遂放弃。

  • 辗转相除法，这里面又包含好几种实现方式。我使用了其中一个我认为最容易理解的方式去实现的。

    我们可以用右图来解释最大公约数的概念：[6]设一个长方形的边长为a和b。因为a和b的任何公约数c都可以整除a和b，所以长方形的边都可以等分为长度为c的线段，也就是长方形可以被边长为c的正方形正好填满。而最大公约数g是所有可能的c中最大的一个。例如，一个24 × 60的长方形区域可以分成1 × 1、2 × 2、3 × 3、6 × 6或12 × 12的正方形网格。也就是说，12是24和60的最大公约数。

这里得补充一句，无论a,b 只要有一个是素数，则最大公约数为1。不然上述概念是有bug的。

  • gcd(a,b)代码会在最后给出

然后看一下最小公倍数的百度百科简介：

最小公倍数
两个或多个整数公有的倍数叫做它们的公倍数。
两个或多个整数的公倍数里最小的那一个叫做它们的最小公倍数。整数a，b的最小公倍数记为[a，b]，同样的，a，b，c的最小公倍数记为[a，b，c]，多个整数的最小公倍数也有同样的记号。
与最小公倍数相对应的概念是最大公约数，a，b的最大公约数记为（a，b）。
关于最小公倍数与最大公约数，我们有这样的定理：
(a,b)[a,b]=ab(a,b均为整数)

  • ps: wiki 上面对于最小公倍数的简介，似乎特别官方，不是很容易理解。于是这里引用百度百科上面的解释。

    • 关键是看最后一句：(a,b)[a,b]=ab(a,b均为整数)。也就是说lcm(a,b) = a*b/gcm(a*b);

    这句太重要了，只要求得最大公约数，立马就可以求出最小公倍数了。/捂脸笑/

  • 装逼开始

    • OK，既然概念理清了，剩下的就是用代码去实现了。

    #include <iostream>

    int add(int a, int b);

    using namespace std;

    //3.1 编写函数IsPrime，判断某个大于2的正整数是否为素数。
    bool isPrime(int num);

    //3.2 编写函数gcd与lcm，分别求两个正整数的最大公约数与最小公倍数。
    int gcd(int a, int b);

    int lcm(int a, int b);

    int main() {
    int a = 20, b = 170, g, lc;
    // cout << "a:";
    // cin >> a;
    // cout << "b:";
    // cin >> b;
        g = gcd(a, b);
        lc = lcm(a, b);
        cout << "gcd(" << a << "," << b << ") = " << g << endl;
        cout << "lcm(" << a << "," << b << ") = " << lc << endl;
    return 0;
    }

    /**
     * 最小公倍数
     * > 求法：lcm = (a*b)/gcd(a,b);
     * from: wiki key:最小公倍数
     * @param a
     * @param b
     * @return
     */
    int lcm(int a, int b) {
    int g = gcd(a, b);
    return a * b / g;
    }

    /**
     * 最大公约数
     * > 求法：a*b = c*c*k = d*d*m = ... = z*z*p; c,d,z 中最大的数字即是最大公约数
     * from: wiki key:辗转相除法
     * @return gcd
     */
    int gcd(int a, int b) {
    // a*b = square = c*c*k;
    int square = a * b;

    int g = 1;
    if (isPrime(a) || isPrime(b)) {
            g = 1;
        } else {
    for (int i = 1; i <= (a > b ? a : b); ++i) {
    int k = square / (i * i);
    if (k * (i * i) == square) {
                    g = i;
                }
            }
        }
    return g;
    }

    bool isPrime(int num) {
        bool prime = true;
    for (int i = 2; i <= num / 2; ++i) {
    if (num % i == 0) {
                prime = false;
            }
        }
    return prime;
    }

    int add(int a, int b) {
    return a + b;
    }

    控制台输出如下：

    gcd(20,170) = 10
    lcm(20,170) = 340

    Process finished with exit code 0
    标签：

    相关文章