C语言经典算法（二）——求最小公倍数的两种方法

清疚 2022-06-03 05:30 128阅读 0赞

今后继续整理算法并写出自己的理解和备注  
C++实现：最小公倍数。C语言同理。

1、 最小公倍数  
<1> 题目描述:求解两个整数(不能是负数)的最小公倍数  
<2> 方法一:穷举法  
<3> 方法二:公式lcm = a \* b / gcd(a,b)

源码：  
一、 最小公倍数  
1、 穷举法

#include<iostream>
    using namespace std;
    unsigned long LCM(unsigned long a, unsigned long b)
    {
        if(a * b == 0)
            return 0;//其中一个数为0，则最小公倍数为0；
        unsigned long lcm = a > b ? a : b;//取出较大的一个
        while(1)
        {
            if((lcm%a==0) && (lcm%b==0))//同时满足整除a和b的数即是所求
                break;      
            lcm++;
        }
        return lcm;
    }
    
    void main()
    {
        unsigned long a,b;
        cout<<"请输入a 和b:>";
        cin>>a>>b;
    
        unsigned long lcm = LCM(a,b);
        cout<<"lcm = "<<lcm<<endl;
    }

2、公式lcm = a \* b / gcd(a,b)

#include<iostream>
    using namespace std;
    unsigned long GCD(unsigned long a, unsigned long b)
    {
        if(b == 0)
            return a;
        else
            return GCD(b, a%b);//可以回归上一篇文章算法（一），这是求最小公约数的方法。
    }
    unsigned long LCM(unsigned long a, unsigned long b)
    {
        if(a * b == 0)
            return 0;
        return (a*b)/GCD(a,b);//使用公式
    }
    
    void main()
    {
        unsigned long a,b;
        cout<<"请输入a 和b:>";
        cin>>a>>b;
    
        unsigned long lcm = LCM(a,b);
        cout<<"lcm = "<<lcm<<endl;
    }