学步园

概念：
　　最小公倍数（Least Common Multiple，缩写L.C.M.），如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数，对于两个整数来说，指该两数共有倍数中最小的一个。计算最小公倍数时，通常会借助最大公约数来辅助计算。
　　两个数的最大公因数和最小公倍数有着下列关系：
　　　　最大公因数×最小公倍数=两数的乘积　　即（a、b）×[a、b]= a×b 

算法(代码)：

#include <stdio.h>
#include <iostream>
#include <math.h>

usingnamespace std;

long GCD( long NumberA, long NumberB );
long LCM( long NumberA, long NumberB );
int main(int argc, char* argv[])
{
long NumberA =18;
long NumberB =17;
long NumberC =12;
long Result =0;
    Result = LCM(NumberA, NumberB);
    cout<<NumberA<<" 与 "<<NumberB<<" 的最小公倍数为:"<<Result<<endl;
    Result = LCM(NumberA, NumberC);
    cout<<NumberA<<" 与 "<<NumberC<<" 的最小公倍数为:"<<Result<<endl;
return0;
}

// 求两数最大公约数,若返回值为1则说明两数为互质数
long GCD( long NumberA, long NumberB )
{
long iDividend = NumberB;                        // 被除数
long iDivisor = NumberA;                        // 除数
long iResidual = iDividend%iDivisor;        //余数
// 辗转相除法
while (iResidual !=0)
    {
//将除数作为被除数
        iDividend=iDivisor;
//把余数作为除数
        iDivisor=iResidual;
//求新的余数
        iResidual=iDividend%iDivisor;
    }
return iDivisor;
}

// 求两数的最小公倍数
long LCM( long NumberA, long NumberB )
{
long Result = NumberA * NumberB / GCD(NumberA, NumberB);
return Result;
}

【参考资料 感谢作者】
http://baike.baidu.com/view/341375.htm