Divisor común más grande de un conjunto de más de 2 enteros

Question

Hay varias preguntas sobre Desbordamiento de pila que tratan sobre cómo encontrar el Divisor común más grande de dos valores. Una buena respuesta muestra un buen recursive function para hacer esto.

Pero, ¿cómo puedo encontrar el GCD de un conjunto de más de 2 enteros? Parece que no puedo encontrar un ejemplo de esto.

---

¿Alguien puede sugerir el código más eficiente para implementar esta función?

static int GCD(int[] IntegerSet) 
{ 
    // what goes here? 
} 

Answer 1

Y aquí tiene un ejemplo de código usando el método LINQ y GCD de la pregunta que ha vinculado. Se está utilizando el algoritmo teórico descrito en otras respuestas ... GCD(a, b, c) = GCD(GCD(a, b), c)

static int GCD(int[] numbers) 
{ 
    return numbers.Aggregate(GCD); 
} 

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

Answer 2

Wikipedia:

El gcd es una función asociativa: gcd (a, gcd (a, c)) = mcd (gcd (a, b), c).

El gcd de tres números se puede calcular como gcd (a, b, c) = gcd (gcd (a, b), c), o en alguna forma diferente mediante la aplicación de conmutatividad y asociatividad. Esto se puede extender a cualquier número de números.

acaba de tomar el máximo común divisor de los dos primeros elementos, a continuación, calcular el máximo común divisor del resultado y el tercer elemento, a continuación, calcular el máximo común divisor del resultado y el cuarto elemento ...

Answer 3

Aquí está la versión de C#.

public static int Gcd(int[] x) { 
     if (x.length < 2) { 
      throw new ArgumentException("Do not use this method if there are less than two numbers."); 
     } 
     int tmp = Gcd(x[x.length - 1], x[x.length - 2]); 
     for (int i = x.length - 3; i >= 0; i--) { 
      if (x[i] < 0) { 
       throw new ArgumentException("Cannot compute the least common multiple of several numbers where one, at least, is negative."); 
      } 
      tmp = Gcd(tmp, x[i]); 
     } 
     return tmp; 
    } 

    public static int Gcd(int x1, int x2) { 
     if (x1 < 0 || x2 < 0) { 
      throw new ArgumentException("Cannot compute the GCD if one integer is negative."); 
     } 
     int a, b, g, z; 

     if (x1 > x2) { 
      a = x1; 
      b = x2; 
     } else { 
      a = x2; 
      b = x1; 
     } 

     if (b == 0) return 0; 

     g = b; 
     while (g != 0) { 
      z= a % g; 
      a = g; 
      g = z; 
     } 
     return a; 
    } 

} 

Fuente http://www.java2s.com/Tutorial/Java/0120__Development/GreatestCommonDivisorGCDofpositiveintegernumbers.htm

Answer 4

Se puede utilizar esta propiedad común de un GCD:

GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b) 

Asumiendo que tiene GCD(a, b) ya definidos es fácil generalizar:

public class Program 
{ 
    static void Main() 
    { 
     Console.WriteLine(GCD(new[] { 10, 15, 30, 45 })); 
    } 

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

    static int GCD(int[] integerSet) 
    { 
     return integerSet.Aggregate(GCD); 
    }  
} 

Answer 5

gcd(a1,a2,...,an)=gcd(a1,gcd(a2,gcd(a3...(gcd(a(n-1),an))))) , entonces lo haría solo paso por paso abortar ing si algunos gcd evalúa a 1.

Si se ordena la matriz, puede ser que sea más rápido para evaluar gcd para un pequeño número anteriores, ya que entonces podría ser más probable que uno gcd evalúa a 1 y se puede parar.

Answer 6

Reescribiendo esto como una sola función ...

static int GCD(params int[] numbers) 
    { 
     Func<int, int, int> gcd = null; 
     gcd = (a, b) => (b == 0 ? a : gcd(b, a % b)); 
     return numbers.Aggregate(gcd); 
    } 

Answer 7

/* 

Copyright (c) 2011, Louis-Philippe Lessard 
All rights reserved. 

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 
Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. 
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 

*/ 

unsigned gcd (unsigned a, unsigned b); 
unsigned gcd_arr(unsigned * n, unsigned size); 

int main() 
{ 
    unsigned test1[] = {8, 9, 12, 13, 39, 7, 16, 24, 26, 15}; 
    unsigned test2[] = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}; 
    unsigned result; 

    result = gcd_arr(test1, sizeof(test1)/sizeof(test1[0])); 
    result = gcd_arr(test2, sizeof(test2)/sizeof(test2[0])); 

    return result; 
} 


/** 
* Find the greatest common divisor of 2 numbers 
* See http://en.wikipedia.org/wiki/Greatest_common_divisor 
* 
* @param[in] a First number 
* @param[in] b Second number 
* @return greatest common divisor 
*/ 
unsigned gcd (unsigned a, unsigned b) 
{ 
    unsigned c; 
    while (a != 0) 
    { 
     c = a; 
     a = b%a; 
     b = c; 
    } 
    return b; 
} 

/** 
* Find the greatest common divisor of an array of numbers 
* See http://en.wikipedia.org/wiki/Greatest_common_divisor 
* 
* @param[in] n Pointer to an array of number 
* @param[in] size Size of the array 
* @return greatest common divisor 
*/ 
unsigned gcd_arr(unsigned * n, unsigned size) 
{ 
    unsigned last_gcd, i; 
    if(size < 2) return 0; 

    last_gcd = gcd(n[0], n[1]); 

    for(i=2; i < size; i++) 
    { 
     last_gcd = gcd(last_gcd, n[i]); 
    } 

    return last_gcd; 
} 

Source code reference

Answer 8

Estos son los tres más comunes usado:

public static uint FindGCDModulus(uint value1, uint value2) 
{ 
    while(value1 != 0 && value2 != 0) 
    { 
      if (value1 > value2) 
      { 
        value1 %= value2; 
      } 
      else 
      { 
        value2 %= value1; 
      } 
    } 
    return Math.Max(value1, value2); 
     } 

    public static uint FindGCDEuclid(uint value1, uint value2) 
     { 
    while(value1 != 0 && value2 != 0) 
    { 
      if (value1 > value2) 
      { 
        value1 -= value2; 
      } 
      else 
      { 
        value2 -= value1; 
      } 
    } 
    return Math.Max(value1, value2); 
    } 

    public static uint FindGCDStein(uint value1, uint value2) 
    { 
    if (value1 == 0) return value2; 
    if (value2 == 0) return value1; 
    if (value1 == value2) return value1; 

    bool value1IsEven = (value1 & 1u) == 0; 
    bool value2IsEven = (value2 & 1u) == 0; 

    if (value1IsEven && value2IsEven) 
    { 
      return FindGCDStein(value1 >> 1, value2 >> 1) << 1; 
    } 
    else if (value1IsEven && !value2IsEven) 
    { 
      return FindGCDStein(value1 >> 1, value2); 
    } 
    else if (value2IsEven) 
    { 
      return FindGCDStein(value1, value2 >> 1); 
    } 
    else if (value1 > value2) 
    { 
      return FindGCDStein((value1 - value2) >> 1, value2); 
    } 
    else 
    { 
      return FindGCDStein(value1, (value2 - value1) >> 1); 
    } 
    } 

Answer 9

Sin usar LINQ.

static int GCD(int a, int b) 
    { 
     if (b == 0) return a; 
     return GCD(b, a % b); 
    } 

    static int GCD(params int[] numbers) 
    { 
     int gcd = 0; 
     int a = numbers[0]; 
     for(int i = 1; i < numbers.Length; i++) 
     { 
      gcd = GCD(a, numbers[i]); 
      a = numbers[i]; 
     } 

     return gcd; 
    } 

Answer 10

int GCD(int a,int b){ 
    return (!b) ? (a) : GCD(b, a%b); 
} 

void calc(a){ 
    int gcd = a[0]; 
    for(int i = 1 ; i < n;i++){ 
     if(gcd == 1){ 
      break; 
     } 
     gcd = GCD(gcd,a[i]); 
    } 
}