1

私はユークリッドのアプローチ、すなわち LCM = num1 * num2 / gcd ( num1 , num2 ) を使用しています。私のアプローチは lcm(a,b,c) = lcm(a,lcm(b,c)) として表すことができますが、このアプローチは they(lcm(a,b,c) and lcm(a,lcm( b,c))) は 2 つの異なる値です。

4

1 に答える 1

0

C++ で次のように、エラトステネスのふるいで 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]
  • 次に、重複する倍数を削除します (たとえば、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;
        }
//--------------------------------------------------------------------------
  • これはふるいよりもはるかに高速です...
于 2015-07-27T07:09:26.067 に答える