小朋友学信奥(4):最小公倍数

科技 100 2017-11-07 15:38

一、最小公倍数(Least Common Multiple)

几个自然数公有的倍数,叫做这几个数的公倍数,其中最小的一个,叫做这几个数的最小的一个,叫做这几个数的最小公倍数。例如:4的倍数有4、8、12、16,……,6的倍数有6、12、18、24,……,4和6的公倍数有12、24,……,其中最小的是12,一般记为[4、6]=12。
12、15、18的最小公倍数是180。记为[12、15、18]=180。

二、编程求两个数的最小公倍数

(一)穷举法

#include <stdio.h>

// 穷举法 
int lcm(int m, int n)
{
    // 取两个数较大的那个。因为最小公倍数不可能比大的那个数还小
    int num = m < n ? n : m;
    // m*n一定是m和n的公倍数,所以做为循环的结束条件 
    for(; num  <= m * n; num++)
    {
        if(0 == num % m && 0 == num % n)
        {
            break;
        }   
    }
    
    return num ;
}


int main() 
{
    int a, b;
    printf("Please input 2 numbers, seperated by space: ");
    scanf("%d %d", &a, &b);
    
    while(a > 0 && b > 0) 
    {
        printf("The least common multiple is: %d\n", lcm(a,b));
        printf("Please input 2 numbers, seperated by space: ");
        scanf("%d %d", &a, &b);
    }
    
    printf("Program will be finished!");
    
    return 0;
}

运行结果:

Please input 2 numbers, seperated by space: 4 6
The least common multiple is: 12
Please input 2 numbers, seperated by space: 7 13
The least common multiple is: 91
Please input 2 numbers, seperated by space: 1000 1500
The least common multiple is: 3000
Please input 2 numbers, seperated by space: 0 0
Program will be finished!

穷举法的优点是思路简单,缺点是效率低。多数情况下,都不能使用穷举法。但是穷举法本身是一种非常重要的思想。

(二)利用最大公约数求最小公倍数

思路:
lcm(a, b) = a * b / gcd(a, b)

例子:
gcd(12, 16) = 4
lcm(12, 16) = 12 * 16 / gcd(12, 16) = 48

程序:

#include <stdio.h>

// 辗转相除法求最大公约数 
int gcd(int m, int n) 
{
    // remainder,余数 
    int remainder; 
    while(n != 0) 
    {
        remainder = m % n;
        m = n;
        n = remainder;
    }
    
    return m;    
}

// 最小公倍数 = 两数相乘 / 最大公约数
int lcm(int x, int y)
{
    return x * y / gcd(x, y);
} 

int main() 
{
    int a, b;
    printf("Please input 2 numbers, seperated by space: ");
    scanf("%d %d", &a, &b);
    
    while(a > 0 && b > 0) 
    {
        printf("The least common multiple is: %d\n", lcm(a,b));
        printf("Please input 2 numbers, seperated by space: ");
        scanf("%d %d", &a, &b);
    }
    
    printf("Program will be finished!");
    
    return 0;
}

运行结果:

Please input 2 numbers, seperated by space: 4 6
The least common multiple is: 12
Please input 2 numbers, seperated by space: 7 13
The least common multiple is: 91
Please input 2 numbers, seperated by space: 1000 1500
The least common multiple is: 3000
Please input 2 numbers, seperated by space: 0 0
Program will be finished!

(三)短除法
思路:

小朋友学信奥(4):最小公倍数-微网络
1.png

左边与底部的因子相乘,即为最小公倍数
所以,12与16的最小公倍数为2 * 2 * 3 * 4 = 48

程序:

#include <stdio.h>

// 短除法 
int lcm(int m, int n) 
{
    int min = m < n ? m : n;
    int s = 1;
    int i;
    for(i = 2; i <= min ; i++)
    {
        // 四个条件只要有一个不满足,while循环结束 
        while(m > 0 && n > 0 && 0 == m % i && 0 == n % i)
        {
            m /= i;
            n /= i;
            s *= i;
        }
    }
    
    return s * m * n;   
}

int main() 
{
    int a, b;
    printf("Please input 2 numbers, seperated by space: ");
    scanf("%d %d", &a, &b);
    
    while(a > 0 && b > 0) 
    {
        printf("The least common multiple is: %d\n", lcm(a,b));
        printf("Please input 2 numbers, seperated by space: ");
        scanf("%d %d", &a, &b);
    }
    
    printf("Program will be finished!");
    
    return 0;
}

运行结果:

Please input 2 numbers, seperated by space: 4 6
The least common multiple is: 12
Please input 2 numbers, seperated by space: 7 13
The least common multiple is: 91
Please input 2 numbers, seperated by space: 1000 1500
The least common multiple is: 3000
Please input 2 numbers, seperated by space: 0 0
Program will be finished!
文章评论