C++ 多个数求最小公倍数

2025-02-07 00:37:46

推荐回答（5个）

回答1：

//你的代码我大概看了一下,估计问题出在所有输入数乘积那
//这个结果sum很容易会很大,超出int范围.
//下面是另一个版本,供参考
#include 
#include 
using namespace std;

int gcd(int a,int b); //最大公约数
int lcm(int a,int b); //最小公倍数:两数乘积=最小公倍数与最大公约数乘积
int  main()
{
    vector  a;//定义向量a用来保存输入数组
    int t,k,n;
    while(cin>>n){
        for(int i=0;i!=n;++i)
        {
            cin>>k;
            a.push_back(k); //保存数据
        }
        t=lcm(a[0],a[1]);   //对向量第0,1元素求最小公倍数
        for(size_t i=2;i!=a.size();++i)
     //求最小公倍数t与向量数组其它元素的最小公倍数
        {
            t=lcm(a[i],t);      
        }
        cout<        a.clear();//清除向量a内容,避免影响下次输入
    }
    return 0;
}   

int gcd(int a,int b) //最大公约数
{
 int r=a%b; 
 while(r){
    a=b;
    b=r;
    r=a%b;
    }
 return b;
}
int lcm(int a,int b) //最小公倍数:两数乘积=最小公倍数与最大公约数乘积
{
    return a*b/gcd(a,b);
}

测试结果:第一行单数是个数,第二行是输入数组,第三行是数组元素的最小公倍数.以此类推

回答2：

程序的问题主要在于算法上出错，另外单词缩写也不正确（最大公约数缩写为GCD，不是GDC），虽然这个不是主要问题。计算最小公倍数的数学公式如下：

最小公倍数 = 两数乘积 / 最大公约数

公式中有两点比较关键：两个数的乘积和最大公约数。很显然，需要将求多个数最小公倍数的问题，转化为求两个数的最小公倍数问题。

而程序中所写，sum代表的乘积，并不是两个数的乘积，而是多个数的乘积，所以是错误的。至于求最大公约数的算法，写得也有些复杂，写法可以简化一些。

下面给出实现的参考示例：

#include 

using namespace std;

int gcd(int a, int b);

int main() {
    int n, num[50], a, b;
    while (cin >> n) {
        if (n <= 1 || n > 50) {
            cout << "n must be [2, 50]" << endl;
            return 1;
        } else {
            cin >> num[0];
            a = num[0];
            for(int i = 1; i < n; i++) {
                cin >> num[i];
                b = num[i];
                a = (a * b) / gcd(a, b);
            }
            cout << a << endl;
        }
    }
    return 0;
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

示例中，对n的输入值做了校验，由于num数组长度为50，且数字个数少于2个无意义，所以限制n的输入范围为2-50的闭区间。

求最小公倍数时，循环num数组，每次计算时，取num数组中元素作为b与a计算，结果存至a中。循环结束后，a即为它们的最小公倍数。

回答3：

求同时n个数的最小公倍数或最大公约数,可采取单独求解的方法,即不要同时使用那种N数之积除以最大公约数的方法(不管用的,它只适合两个或少量的数才有效，因为数字越多就越容易发生内存溢出):

回答4：

1、输入n个数，不是只定义一个50大小的数组，需要你动态分配数组
2、i=0没有处理，当i=0时 r=0 sum/r 是没有意义的
3、对于输入数字没有控制
4、求最小公倍数的算法是不对的，多个非负整数的最小公倍数不能简单的用“总的乘积/最大公约数”来求得，比如｛2，3，4｝如果按照你的方法，算出来的最大公约数是1，按照2*3*4/1求得的最小公倍数是24，事实上他们的最小公倍数是12。
求多个数最小共倍数的算法为：
（1）计算m=a1*a2*..*an
（2）把a1,a2,..,an中的所有项ai用m/ai代换
（3）找到a1,a2,..,an中的最小非零项aj，若有多个最小非零项则任取一个
（4） aj以外的所有其他非0项ak用ak mod aj代替；
若没有除aj以外的其他非0项，则转到（6）
（5）转到（3）
（6）最小公倍数为m/aj

回答5：

首先你的代码求得不是最小公倍数，而是最大公约数。要求a和b的最小公倍数，可以用

a*b / GCD(a, b)来求。其次，你那个最多也就能求50个数的。

#include 
using namespace std;
int GCD(int num1,int num2)
{
    if(num2 > num1)
    {
        int t = num2;
        num2 = num1;
        num1 = t;
     }
    if(num1%num2==0)
        return num2;
    else return  GCD(num2,num1%num2);
}
int LCM(int a,int b)//求a。b最小公倍数
{
    int temp_lcm;
    temp_lcm=a*b/GCD(a,b);//最小公倍数等于两数之积除以最大公约数
       return temp_lcm;
}
int main()
{
    int N;
    cin >> N;
    int *arr = new int[N];
    for(int i = 0;i!= N; ++i)
        cin >> arr[i];
    int ans = LCM(arr[0], arr[1]);
    for(int  i = 2; i != N; ++i)
        ans = LCM(ans, arr[i]);
    cout << ans << endl;
    delete []arr;
    return 0;
}

最新问答

熊猫烧香作者李俊出狱后会有怎么样的前途

我跟我女朋友谈了六年了，我脾气暴躁，我两是从高中开始谈恋爱的，一直异地到她大三，高中的时候我经常管

求助Y460换CPU开机需要按F1

游戏原画，影视动画和商业插画哪个前景比较好？

红茶和绿茶的区别是什么？

华润置地公馆周边环境怎么样？生活便利吗？

PS调色滤镜Color Efex怎么用

我QQ号换头像了，为什么腾讯视频上显示还是原来的企鹅?

苹果6打电话没有声音，而免提才有声音，为什么？

开一家设计公司需要多少资金？