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

Question

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

Answer 1

Debe usar Lehmer's GCD algorithm.

Answer 2

Sin recursividad:

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 tenedor-join, donde se divide la matriz y calcular GCDS en paralelo. He aquí algo de 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); 
    } 
} 

Answer 3

Es posible que desee ordenar los números primero y calcular el máximo común divisor de forma recursiva a partir de los dos números más pequeños.

Answer 4

Si tiene mucho de 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); 

(que funciona para algunos ejemplos, pero no realmente a prueba)

Answer 5

Aquí era 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 programas cuando hice esto.

La optimización que se necesitaba aquí era que la recursión se resolviera utilizando un algoritmo de multiplicación de matriz rápida.

Answer 6

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; 
} 

Answer 7

C++ 17

He escrito esta función para calcular gcd de n números utilizando C++ 's en __gcd construido (int a, int b) función.

int gcd(vector<int> 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 this link.

Consulte también Dijkstra's GCD algorithm desde el siguiente enlace. Funciona sin división. Así que podría ser un poco más rápido (Por favor, corríjanme si estoy equivocado.)

Answer 8

//Recursive solution to get the GCD of Two Numbers 

long long int gcd(long long int a,long long int b)<br> 
{ 
    return b==0 ? a : gcd(b,a%b); 
} 
int main(){ 
    long long int a,b; 
    cin>>a>>b; 
    if(a>b) cout<<gcd(a,b); 
    else cout<<gcd(b,a); 
return 0; 
} 

Answer 9

Utilice la algoritmo de Euclides:

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

lo aplica para los dos primeros números, entonces 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); 

Answer 10

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<n;i++){ 
      arr[i]=sc.nextInt(); 
     } 
     System.out.println(calculateGCD(arr)); 
    } 
} 

**

Above is the java working code .....el pseudo código de los cuales es ya mencionan por https://stackoverflow.com/users/7412/dogbane

**

Answer 11

A continuación está el código fuente del programa de C para encontrar HCF de N números utilizando matrices.

#include<stdio.h> 
 

 
int main() 
 
{ 
 
    int n,i,gcd; 
 
    printf("Enter how many no.s u want to find gcd : "); 
 
    scanf("%d",&n); 
 
    int arr[n]; 
 
    printf("\nEnter your numbers below :- \n "); 
 
    for(i=0;i<n;i++) 
 
    { 
 
     printf("\nEnter your %d number = ",i+1); 
 
     scanf("%d",&arr[i]); 
 
    } 
 
    gcd=arr[0]; 
 
    int j=1; 
 
    while(j<n) 
 
    { 
 
     if(arr[j]%gcd==0) 
 
     { 
 
      j++; 
 
     } 
 
     else 
 
     { 
 
      gcd=arr[j]%gcd; 
 
      i++; 
 
     } 
 
    } 
 
    printf("\nGCD of k no.s = %d ",gcd); 
 
    return 0; 
 
}

Para más referencia a esta website para más aclaraciones .......

Answer 12

Puede utilizar 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. (Suponiendo que todo num en la lista están 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 

Answer 13

A recursiva JavaScript (ES6) de una sola línea para cualquier número de dígitos.

const gcd = (a, b, ...c) => b ? gcd(b, a % b, ...c) : c.length ? gcd(a, ...c) : Math.abs(a);