Huge Lemon的博客

最小公倍数&最大公因数

2020-01-21

几个数共有的倍数叫做这几个数的公倍数，其中除0以外最小的一个公倍数，叫做这几个数的最小公倍数。如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。约数和倍数都表示一个整数与另一个整数的关系，不能单独存在。

求最大公因数算法

求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。
下面介绍辗转相除法（欧几里德算法）

有两整数a和b：
① a%b得余数temp
② 若temp=0，则b即为两数的最大公因数
③ 若temp≠0，则令a=b，b=temp，再回去执行①

例如，求27和15的最大公因数过程为：

27÷15=1 余12
15÷12=1 余3
12÷3=4 余0
因此，3即为最大公因数

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
//求a，b的最大公因数
int GCD(int a, int b) {
    int temp;
    do {
        temp = a % b;
        if(temp == 0)
            return b;
        else {
            a = b;
            b = temp;
        }
    } while(temp != 0);
}

求最小公倍数算法

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
//求m和n的最小公倍数
int LCM(int m, int n) {
    int x, y, c;
    x = m; y = n;
    while(m != 0) {
        c = n % m;
        n = m;
        m = c;
    }
    return (x * y / n);
}
Tags: 算法
← 文件分配方式之索引分配 寻找旋转排序数组中的最小值 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏