Comment trouver le GCD de quelques paires de nombres d'un ensemble donné?

Question

Je peux calculer le GCD de deux nombres. étant donné un ensemble S = {1,2,3,4,5} et je dois calculer le GCD de chaque paire comme {1,2} = 1, {1,3} = 1, {1,4} = 1 , {1,5} = 1, {2,3} = 1, {2,4} = 2, {2,5} = 1 et ainsi de suite. Je connais la solution O (N^2) en calculant simplement le GCD de chaque paire qui me donnera TLE en cas de grand ensemble pour 2 < = n < = 10^9 ou plus mais je veux apprendre O (N * sqrt (N)) ou mieux. Je veux le GCD de chaque paire séparément.

Answer 1

Vous pouvez écrire un programme avec Euclidean algorithm

Découvrez l'exemple de trouver GCD(1071,462)

GCD {1,2,3,4,5} = {GCD GCD {{1,2} GCD, GCD {3,4}}, 5}

utilisation Euclidean algorithm 4 fois seulement calclate le PGCD de l'ensemble donné S = {1,2,3,4,5}

En utilisant euclidienne, la seule Ce que vous devez faire est de trouver les rappels jusqu'à ce que le nombre soit discutable.

Answer 2

L'algorithme euclidien de base doit aider.

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

Fait intéressant si vous voulez trouver le GCD de l'ensemble complet. Tout ce que vous avez à faire est de former un sous-ensemble à partir du GCD obtenu et de l'itérer à moins qu'il ne reste qu'un seul élément final. par exemple S={1,2,3,4,5} => S1={GCD(1,2) , GCD(3,4) , add 5 } => S2={GCD(1,1) , and 5 } => S3={GCD(1,5)} => 1