quel est le moyen le plus rapide de trouver le pgcd de n nombres ?

Question

Quel est le moyen le plus rapide de calculer le plus grand commun diviseur de n nombres ?

Answer 1

Sans récursivité :

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

Pour les très grands tableaux, il peut être plus rapide d'utiliser le modèle fork-join, dans lequel vous divisez votre tableau et calculez les pgcd en parallèle. Voici un pseudo-code :

 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 2

Vous pouvez d'abord trier les nombres et calculer le pgcd de manière récursive en partant des deux plus petits nombres.

Answer 3

Vous devez utiliser l'algorithme GCD de Lehmer .