最小公倍數

维基百科,自由的百科全书
跳转至: 导航搜索

最小公倍數数论中的一个概念。若有一個數字 X,可以被另外兩個數字 A、B 整除,且 X 大於 A 和 B,則 X 為 A 和 B 的公倍數。A 和 B 的公倍數可以有很多個,而所有的公倍數中,最小的公倍數就叫做最小公倍數。兩個整數公有的倍數称为它们的公倍数,其中最小的一個正整数称为它们两个的最小公倍数。同样地,若干个整数公有的倍数中最小的正整数称为它们的最小公倍数。n个整数a_1, a_2, \cdots , a_n的最小公倍数一般记作:[a_1, a_2, \cdots , a_n],或者参照英文记法记作\operatorname{lcm}(a_1, a_2, \cdots , a_n),其中lcm是英语中“最小公倍数”一词(lowest common multiple)的首字母缩写。

例如,十天干和十二地支的混合稱为一个陰曆,干支循環回歸同一名稱的所需時間,就是1210的最小公倍數,即是60──一個「甲子」。

分數进行加減运算時,要求兩數的分母相同才能計算,故需要通分;标准的计算步骤是将兩個分數的分母通分成它们的最小公倍數,然后将通分后的分子相加。

与最大公约数的关系[编辑]

两个整数的最小公倍数与最大公约数之间有如下的关系

\operatorname{lcm}(a,b)=\frac{|a\cdot b|}{\operatorname{gcd}(a,b)}

计算方法[编辑]

最小公倍数可以通过多种方法得到,最直接的方法是列举法,从小到大列举出其中一个数(如最大數)的倍数,当这个倍数也是另一个数的倍数时,就求得最小公倍数。另一个方法是利用公式\operatorname{lcm}(a_1,a_2)=\frac{a_1 a_2 }{\gcd(a_1,a_2)}来求解,这时首先要知道它们的最大公因数。而最大公约数可以通过短除法得到。

利用整数的唯一分解定理,还可以用質因數分解法。将每个整数进行质因数分解。对每个质数,在质因数分解的表达式中寻找次数最高的乘幂,最后将所有这些质数乘幂相乘就可以得到最小公倍数。譬如求216384210的最小公倍數。对216384210来说:

216=2^3 \times 3^3384=2^7 \times 3^1210=2^1 \times 3^1 \times 5^1 \times 7^1
其中2 对应的最高次乘幂为2^73 对应的最高次乘幂为3^357 对应的最高次乘幂分别是5^17^1。将这些乘幂乘起来,就可以得到最小公倍数:
[216, 384, 210]=2^7 \times 3^3 \times 5^1 \times 7^1 = 120960

程序计算方法:[编辑]

最笨的方法:在两个数中,选那个大的数,然后去除以那个小的数,如果能整除,那么最小公倍数就是 那个大的数,如果不能,就把那个大的数乘以2,再去除以那个小的数,如果还不能整除,那么就把大 的数乘以3,...一直到把那个大的数乘以那个小的数。

c#语言部分:

       public static float minGongBeiShu(int n1, int n2)
       {
           int temp = Math.Max(n1, n2);
           n2 = Math.Min(n1, n2);//n2中存放两个数中最小的
           n1 = temp;//n1中存放两个数中最大的
           int product = n1 * n2;//求两个数的乘积
           while (n2 != 0)
           {
               n1 = n1 > n2 ? n1 : n2;//使n1中的数大于n2中的数
               int m = n1 % n2;
               n1 = n2;
               n2 = m;
           }
           return (product / n1);//最小公倍数
       }

C语言部分:

1int lcm(int a,int b)
{
    int max = (a >= b?a:b),min = (a < b?a:b),i;
    for(i = 1;;++i)
    {
        if((max * i) % min == 0)
        {
            return (max * i);
        }
    }
}
 
2#include <stdio.h>
int GCD(int a,int b);
int LCM(int a,int b);
int main()
{
    int num1,num2,gcd,lcm;
    printf("求两个数的[[最大公约数]]及最小公倍数 nn请输入你想计算的两个数:n");
    scanf("%d%d",&num1,&num2);
    if(num1<num2)
    {
        gcd=num1;num1=num2;num2=gcd;
    }
    gcd=GCD(num1,num2);
    lcm=LCM(num1,num2);
    printf("最大公约数为:%d n最小公倍数为:%dn",gcd,lcm);
}
 
int GCD(int a,int b)
{
    if ( num1 % num2 == 0)
    {
        return num2; 
    }
    else
        return GCD ( num2,num1 % num2) ;
}
 
int LCM(int a,int b)
{
    int temp_lcm;
    temp_lcm=a*b/GCD(a,b); //最小公倍数等于两数之积除以最大公约数
    return temp_lcm;
}
 
 
3、这个代码最少:
//求最大公约数:
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
 
//求最小公倍数:
int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}
 
4/* 用欧几里德算法求最大公约数 */
unsigned gcd1(unsigned x,unsigned y)
{
    unsigned temp;
    while(y!=0){ /* 辗转相除 */
        temp=y;
        y=x%y;
        x=temp;
    }
    return x;
}
 
5、快速的位运算方法:
/* 用更快的位运算求最大公约数,没有用任何的除法运算 */
 
#include <stdio.h>
unsigned gcd2(unsigned x,unsigned y)
{
    unsigned temp;
    unsigned power_of_two=0;
 
    if(x==0)  return y;  /* 有一个为0的特殊情况 */
    if(y==0)  return x;
 
    /* 求x和y的最大的公共幂因子2**powoftwo(**表示求幂) */
    while(((x | y) & 1)==0){ /* 末位为0时,说明是偶数,还有因子2 */
        x>>=1;  /* 除以2 */
        y>>=1;
        ++power_of_two;
    } /* 循环结束时x和y中必一个为奇数 */
 
    while((x & 1)==0) /* 若x仍为偶数,则让x变成奇数 */
        x>>=1; 
 
    /* 对剩下的x和y,用最大公约数的性质(x,y)=(y,x-y)来求x和y的最大公约数 */
    while(y){
        /* x为奇数,且y为非0 */
        while((y & 1)==0)
            y>>=1;  /* 让y变成奇数 */
 
        /* 现在剩下的x和y均为奇数 */
        temp=y;
        if(x>y)
            y=x-y;
        else
            y=y-x;
        x=temp;
    }
    return (x<<power_of_two); /* 返回原先x和y的最大公约数 */
}
 
/* 求最小公倍数 */
unsigned lcm(unsigned x,unsigned y)
{
    return x*y/gcd2(x,y);
}
 
int main(){
    printf("%un",gcd1(16,24));
    printf("%un",gcd2(16,24));
    printf("%un",lcm(16,24));
    return 0;
}

PASCAL语言实现:

1var a,b,ans:integer;
function gcd(a,b:integer):longint;
begin
    if b=0 then gcd:=a
    else gcd:=gcd(b,a mod b ) ;
end;
2var a,b,ans:integer;
function gcd(a,b:integer):longint;
begin
    readln(a,b );
    ans:=(a*b) div gcd(a,b);
    write(ans);
end;


C++程序实现

#include <iostream>
using namespace std;
int GCD(int a,int b);
int LCM(int a,int b);
int main()
{
    int num1,num2,gcd,lcm;
    cout<<"求两个数的最大公约数及最小公倍数"<<endl<<endl;
    cout<<"请输入两个数:";
    cin>>num1>>num2;
    gcd=GCD(num1,num2);
    lcm=LCM(num1,num2);
    //输出最大公约数和最小公倍数
    cout<<"最大公约数为:"<<gcd<<endl;
    cout<<"最小公倍数为:"<<lcm<<endl;
    system("pause");
    return 0;
}
 
int GCD(int a,int b)
{
    if ( num1 % num2 == 0)    return num2; 
    else return GCD ( num2,num1 % num2) ;
}
 
int LCM(int a,int b)
{
    int temp_lcm;
    temp_lcm=a*b/GCD(a,b); //最小公倍数等于两数之积除以最大公约数
    return temp_lcm;
}

应用[编辑]

求最小公倍数是进行分数加减法时的步骤之一。将分母通分时,会把所有分数的分母通分为它们的最小公倍数,然后将分子相加。例如:

{2\over21}+{1\over6}={4\over42}+{7\over42}={11\over42}

其中分母42就是216的最小公倍数。

参见[编辑]

参考来源[编辑]

  • 柯召,孙绮,孙琦. 《数论讲义》. 高等教育出版社. 2005年. ISBN 753205473X. 
  • 阿尔伯特﹒H﹒贝勒著 谈祥柏译. 《数论妙趣:数学女王的盛情款待》. 上海教育出版社. 1998年. ISBN 7040091909.