algorithm - 如何使用 GCD 方法查找多个数字的 lcm？

Question

我正在使用欧氏方法，即 LCM = num1 * num2/gcd ( num1 , num2 )我已经成功地为两个数字编写了代码，但是如果我尝试将其用于多个输入，它就会出现问题。我的方法可以表示为lcm(a,b,c) = lcm(a,lcm(b,c))但这种方法不起作用，因为它们(lcm(a，b，c)和 lcm(a，lcm(b，c)))是两个不同的值。

Answer 1

我在 C++ 中通过 Sieves of Eratosthenes 计算 LCM:

int lcm(int *a,int N,bool _sorted=false)    // least common multiple of a[N]
    {                                       // if sorted a[N] must be: (a0 > a1 > a2 > ... > aN)
    if (N<1) return 0;
    int i,j,c,dc;
    int *b=new int[N];
    if (_sorted) for (i=0;i<N;i++) b[i]=a[i];   // b[N] = a[N]
    else for (c=0x7FFFFFFF,j=0;j<N;j++,c=dc)    // b[N] = insert sort a[N]
        {
        for (dc=0,i=0;i<N;i++)
         if ((dc<a[i])&&(c>a[i])) dc=a[i];
        if (!dc) { N=j; break; }
        b[j]=dc;
        }
    // replace duplicit multiplies with 1
    for (i=  0;i<N;i++) if (b[i]>1)
    for (j=i+1;j<N;j++) if (b[j]>1)
     if (b[i]%b[j]==0) b[j]=1;
    // cut off all ones
    for (j=0,i=0;i<N;i++) if (b[i]>1) { b[j]=b[i]; j++; } N=j;
    if (N<1) return 1;
    // lcm
    for (dc=b[0],i=-1,c=dc;i<0;c+=dc)
     for (i=1;i<N;i++)
      if (c%b[i]!=0) { i=-1; break; }
    c-=dc;
    delete[] b;
    return c;
    }

• 首先确保输入的数字是降序排列的(b[] 数组)
• 它是旧代码的遗留物，您只需要在 b[0]
中拥有最大的 num
• 然后删除重复的倍数(例如 8、4、2 ... 仅使用 8)
• 最后使用筛子
• 您实际上不需要将筛子存储在内存中
• 而是逐步计算筛分
• 并且只记住最大数的倍数 c
• 如果剩下的所有数字都可以整除你就找到了结果

[edit2] gcd 的使用

//--------------------------------------------------------------------------
int gcd(int a0,int a1)
    {
    int d,r,r0;
    if (a0<a1) { r=a0; a0=a1; a1=r; }
    // euklid a0/a1
    d=a0/a1;
    r=a0%a1; r0=r;
    if (!r) return a1;
    // a1/r0
    d=a1/r0;
    r=a1%r0;
    if (!r) return r0;
    a0=r0; a1=r;
    for (;;)
        {
        if (a0<a1) { r=a0; a0=a1; a1=r; }
        d=a0/a1;
        r=a0%a1;
        if (!r) return a1;
        a0=a1; a1=r;
        }
    return 0;
    }
//--------------------------------------------------------------------------    
int lcm(int *a,int N)                               // least common multiple of a[N]
        {
        int a0,a1,aa;
        if (N==0) return 0;
        if (N==1) return a[0];
        a0=a[0];
        if (N==2) a1=a[1]; else a1=lcm(a+1,N-1);
        aa=gcd(a0,a1);
        if (N==2) return (a0*a1)/aa;
        return (a1/aa)*a0;
        }
//--------------------------------------------------------------------------

• 这比筛子快得多......