¿Cuál es la forma más rápida de encontrar el gcd de n números?

¿Cuál es la forma más rápida de calcular el mayor divisor común de n números?

Deberías usar el algoritmo GCD de Lehmer .

Sin recursión:

 int result = numbers[0]; for(int i = 1; i < numbers.length; i++){ result = gcd(result, numbers[i]); } return result; 

Para matrices muy grandes, podría ser más rápido utilizar el patrón de unión de horquilla, donde se divide la matriz y se calculan gcds en paralelo. Aquí hay un pseudocódigo:

 int calculateGCD(int[] numbers){ if(numbers.length <= 2){ return gcd(numbers); } else { INVOKE-IN-PARALLEL { left = calculateGCD(extractLeftHalf(numbers)); right = calculateGCD(extractRightHalf(numbers)); } return gcd(left,right); } } 

Es posible que desee ordenar los números primero y calcular el gcd recursivamente a partir de los dos números más pequeños.

Si tiene muchos números pequeños , la factorización puede ser realmente más rápida.

 //Java int[] array = {60, 90, 45}; int gcd = 1; outer: for (int d = 2; true; d += 1 + (d % 2)) { boolean any = false; do { boolean all = true; any = false; boolean ready = true; for (int i = 0; i < array.length; i++) { ready &= (array[i] == 1); if (array[i] % d == 0) { any = true; array[i] /= d; } else all = false; } if (all) gcd *= d; if (ready) break outer; } while (any); } System.out.println(gcd); 

(funciona para algunos ejemplos, pero no realmente probado)

Usa el algoritmo euclidiano :

 function gcd(a, b) while b ≠ 0 t := b; b := a mod b; a := t; return a; 

Lo aplicas para los primeros dos números, luego el resultado con el tercer número, etc …:

 read(a); read(b); result := gcd(a, b); i := 3; while(i <= n){ read(a) result := gcd(result, a); } print(result); 

Puedes usar divide y vencerás. Para calcular gcdN ([]), divide la lista en primera mitad y segunda mitad. si solo tiene un num para cada lista. calcula usando gcd2 (n1, n2).

Acabo de escribir un código de muestra rápido. (asumiendo que todos los números en la lista son Ints positivos)

 def gcdN(nums): n = len(nums) if n == 0: return "ERROR" if n == 1: return nums[0] if n >= 2: return gcd2(gcdN(nums[:n//2]), gcdN(nums[n//2:])) def gcd2(n1, n2): for num in xrange(min(n1, n2), 0, -1): if n1 % num == 0 and n2 % num == 0: return num 

C ++ 17

He escrito esta función para calcular gcd de n números usando C ++ en la función __gcd (int a, int b).

 int gcd(vector vec, int vsize) { int gcd = vec[0]; for (int i = 1; i < vsize; i++) { gcd = __gcd(gcd, vec[i]); } return gcd; } 

Para saber más sobre esta función, visite este enlace .

También consulte el algoritmo GCD de Dijkstra desde el siguiente enlace. Funciona sin división. Por lo tanto, podría ser un poco más rápido (Corrígeme si estoy equivocado).

Aquí hay un método gcd que usa la propiedad que gcd (a, b, c) = gcd (a, gcd (b, c)).
Utiliza el método gcd de BigInteger porque ya está optimizado.

 public static BigInteger gcd(BigInteger[] parts){ BigInteger gcd = parts[0]; for(int i = 1; i < parts.length; i++) gcd = parts[i].gcd(gcd); return gcd; } 
 //Recursive solution to get the GCD of Two Numbers long long int gcd(long long int a,long long int b)
{ return b==0 ? a : gcd(b,a%b); } int main(){ long long int a,b; cin>>a>>b; if(a>b) cout<

A continuación, se muestra el código fuente del progtwig C para encontrar HCF de N números utilizando matrices.

 #include int main() { int n,i,gcd; printf("Enter how many no.su want to find gcd : "); scanf("%d",&n); int arr[n]; printf("\nEnter your numbers below :- \n "); for(i=0;i 

Un JavaScript recursivo (ES6) de una sola línea para cualquier cantidad de dígitos.

 const gcd = (a, b, ...c) => b ? gcd(b, a % b, ...c) : c.length ? gcd(a, ...c) : Math.abs(a); 
 import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class GCDArray{ public static int [] extractLeftHalf(int [] numbers) { int l =numbers.length/2; int arr[] = Arrays.copyOf(numbers, l+1); return arr; } public static int [] extractRightHalf(int [] numbers) { int l =numbers.length/2; int arr[] = Arrays.copyOfRange(numbers,l+1, numbers.length); return arr; } public static int gcd(int[] numbers) { if(numbers.length==1) return numbers[0]; else { int x = numbers[0]; int y = numbers[1]; while(y%x!=0) { int rem = y%x; y = x; x = rem; } return x; } } public static int gcd(int x,int y) { while(y%x!=0) { int rem = y%x; y = x; x = rem; } return x; } public static int calculateGCD(int[] numbers){ if(numbers.length <= 2){ return gcd(numbers); } else { int left = calculateGCD(extractLeftHalf(numbers)); int right = calculateGCD(extractRightHalf(numbers)); return gcd(left,right); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr[] = new int[n]; for(int i=0;i 

**

Arriba está el código de trabajo de Java ..... el pseudo código del cual ya se menciona por https://stackoverflow.com/users/7412/dogbane

**

Aquí estaba la respuesta que estaba buscando. La mejor manera de encontrar el gcd de n números es, de hecho, utilizando recursion.ie gcd (a, b, c) = gcd (gcd (a, b), c). Pero estaba obteniendo tiempos de espera en ciertos progtwigs cuando hice esto.

La optimización que se necesitaba aquí era que la recursión se debía resolver usando un algoritmo de multiplicación de matriz rápida.