多个数的最小公倍数（大数相乘）

我会带着你远行 2022-06-02 05:21 154阅读 0赞

为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。
    但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。
    事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。
     
    我们希望寻找到能除尽1至n的的每个数字的最小整数。
     
    不要小看这个数字，它可能十分大，比如n=100, 则该数为：
    69720375229712477164533808935312303556800
     
    请编写程序，实现对用户输入的 n （n<100）求出1~n的最小公倍数。
     
    例如：
    用户输入：
    6
    程序输出：
    60
     
    用户输入：
    10
    程序输出：
    2520
    
     
     #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int lu[2000];
    int a[105];
    int main()
    {
        int i,j;
        for(i=1; i<=101; i++)
            a[i]=i;
        //求多个数最小公倍数的核心思想,两种写法一样的
        //如果后面出现的i是前面出现的i的倍数,就除以它，取商代替之
        //最后求多个输的最小公倍数的时候，就可以直接相乘了,只需注意要不要用大数来处理
        for(int i=3;i<=101;i++){
            for(int j=i-1;j>=2;j--){
                if(a[i]%a[j]==0)
                    a[i]=a[i]/a[j];
            }
        }
        /*for(i=2; i<=101; i++)
            for(j=i+1; j<=101; j++)
                if(a[j]%a[i]==0)
                    a[j]=a[j]/a[i];*/
        /*for(int i=1;i<101;i++){
            printf("%d ", a[i]);
        }*/
        int n;
        while(~scanf("%d",&n))
        {
            memset(lu,0,sizeof(lu));
            lu[0]=1;
            //下面是常用的大数相乘
            for(i=2; i<=n; i++)
            {
                int c=0;
                for(j=0; j<1700; j++)
                {
                    int  s=lu[j]*a[i]+c;//大数的最基本算法
                    lu[j]=s%10;
                    c=s/10;
                }
            }
            //非零就break;
            for(i=1700-1; i>=0; i--)
                if(lu[i])
                    break;
            for(j=i; j>=0; j--)
                printf("%d",lu[j]);//逆序输出答案
            printf("\n");
        }
    }