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

Question

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

Answer 1

我在 C++ 中通过 Eratosthenes 的 Sieves 计算 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[]数组）
• 它是旧代码的剩余部分，您只需要在其中拥有最大的 numb[0]
• 然后删除重复的倍数（例如 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;
        }
//--------------------------------------------------------------------------

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