Trouver le plus grand diviseur commun dans une plage donnée

Le problème indique que nous devons trouver le GCD dans une plage donnée. Nous obtiendrons deux entiers positifs x et y et deux entiers p et q dans la plage [p,q]. Nous devons trouver le PGCD (plus grand diviseur commun) des nombres x et y compris dans la plage [p,q]. PGCD, connu en mathématiques comme le plus grand diviseur commun, est le plus grand entier positif qui divise deux entiers positifs donnés. L'entier donné ne doit pas être nul. Pour deux entiers positifs x et y, il est exprimé par pgcd(x,y).

Par exemple, nous avons deux entiers positifs 6 et 9. Le plus grand diviseur commun pgcd(6,9) sera 3 car c'est le plus grand nombre qui divise ces deux nombres.

Mais dans ce problème, nous devons trouver le plus grand commun diviseur de deux entiers positifs donnés dans une plage spécifiée. Comprenons ce problème à travers un exemple. Nous recevrons 4 nombres en entrée x et y pour trouver le pgcd de ces nombres et deux nombres indiquant la plage du pgcd, c'est-à-dire [p, q].

Entrée : x=8, y=12, p=1, q=3

Sortie : 2

Explication - Puisque le plus grand diviseur commun des deux nombres donnés x et y est 4. Mais 4 n'est pas dans la plage [1,3]. Le plus grand diviseur commun dans la plage [1,3] est 2, ce qui correspond au résultat souhaité.

Entrée : x=17, y=15, a=5, b=10

Sortie : -1

Explication - Le plus grand diviseur commun des nombres 17 et 15 est 1. Parce que 1 n'est pas dans la plage donnée [5,10]. Lorsqu'il n'y a pas de diviseur commun dans la plage donnée, nous devons imprimer -1 en sortie.

Algorithme

L'algorithme que nous utilisons pour résoudre le problème est très simple et mathématiquement lié. Tout d’abord, nous trouverons le pgcd (plus grand diviseur commun) des nombres x et y. En C++, il existe une fonction intégrée appelée gcd() qui renvoie le plus grand diviseur commun des nombres en sortie.

Grammaire

int divisor=gcd(x,y);

Nous pouvons également utiliser la méthode efficace de l'algorithme d'Euclide pour trouver le pgcd de deux nombres. Les deux fonctionnent en même temps et la complexité temporelle est O(log(min(x,y)).

Maintenant, nous pouvons utiliser des lois simples de l'arithmétique pour conclure qu'un nombre qui divise le pgcd de deux nombres sera également divisé par les deux nombres eux-mêmes . Ainsi, itérer de i=1 à sqrt(gcd(x,y)) dans une boucle for nous aidera à obtenir tous les diviseurs communs du nombre.

Ensuite, vérifiez si chaque i jusqu'à sqrt(gcd(x,y)) i divise pgcd(x,y). Si je divise pgcd(x,y), alors on peut dire que pgcd(x,y)/i sera également le diviseur de pgcd, concluant ainsi qu'il est aussi le diviseur commun des nombres x et y.

Comprenons ce concept à travers un exemple. Supposons que x et y valent respectivement 32 et 48. pgcd (18,27) est 16. Donc dans ce cas, nous allons parcourir de i=1 à i<=4, ce qui est sqrt(16). Considérons i=2. Ici, je divise par pgcd(18,27), qui est 16/2, ce qui équivaut à 8. Par conséquent, pgcd(x,y)/i divise également pgcd(x,y) pour obtenir i. <=4，即 sqrt(16)。让我们考虑 i=2。这里我除以 gcd(18,27)，即 16/2，等于 8。因此 gcd(x,y)/i 也会除 gcd(x,y) 得到 i。

Remarque - Si le nombre n est divisé par n'importe quel nombre x pour obtenir y, qui peut être exprimé comme $frac{n}{x}:=:y$ alors y divisera n par x $(x:times : y:=:n)$.

Cet algorithme est probablement le moyen le plus efficace de résoudre ce problème. Tout en suivant cet algorithme, nous vérifierons constamment si le dénominateur commun est dans la plage [a,b]. Sinon, nous utiliserons la fonction max() pour mettre à jour en permanence le diviseur dans la variable afin d'obtenir le plus grand diviseur commun de la plage.

Syntaxe de la fonction max()

int m = max(a,b);

Il renvoie la valeur maximale de a et b.

Méthode

Voici l'approche que nous suivrons -

• Initialisez une fonction pour calculer le plus grand diviseur commun dans une plage donnée.

• Calculez le pgcd de deux nombres positifs donnés x et y.

• Initialisez le nom de la variable ans = -1.

• Parcourez de i=1 à i<=sqrt(gcd(x,y)) dans la boucle for et continuez à vérifier si je divise pgcd(x,y). <=sqrt(gcd(x,y)) 并不断检查 i 是否整除 gcd(x,y)。

• Si (gcd(x,y)%i)=0, vérifiez si i est dans la plage [a,b] et utilisez la fonction max() pour le stocker dans ans afin que nous obtenions le plus grand diviseur commun situé à dans la plage.

• Vérifiez également si gcd/i est dans la plage, s'il est dans la plage, utilisez à nouveau la fonction max() pour mettre à jour la valeur de ans.

• Retournez après avoir terminé toutes les itérations de la boucle for.

Exemple

Implémentation de cette méthode en C++ -

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

// to calculate gcd of two numbers using Euclidean algorithm
int gcd(int a, int b){
   if(a == 0)
   return b;
   return gcd(b % a, a);
}

//function to calculate greatest common divisor in the given range [a,b]
int build(int x, int y, int a, int b) {

   //using C++ inbuilt library to calculate gcd of given numbers
   int z = gcd(x, y); //we can use euclidean algorithm too as an alternative
   int ans = -1; //storing -1 for the case when no common divisor lies in the range
   for(int i = 1; i<=sqrt(z); i++) { //iterating until sqrt(z) because either of two factors
      //of a number must be less than square root of the number
      if(z % i == 0) {
         if(i >= a && i <= b) //checking it i lies in the range
         ans = max(ans, i); //storing maximum value
         if((z / i) >= a && (z / i) <= b)
         ans = max(ans, z / i);
      }
   }
   return ans;
}
int main() {
   int x, y, a, b;
   x=24, y=42, a=3, b=9;
   cout << build(x, y, a, b) <<" is the gcd that lies in range ["<<a<<","<<b<<"]"<<endl;
   return 0;
}

Sortie

6 is the gcd that lies in range [3,9]

Complexité temporelle : O(log(min(x,y)) + sqrt(z)), où z est le plus grand diviseur commun de deux nombres x et y.

Complexité de l'espace : O(1), car aucun espace supplémentaire n'est utilisé.

Conclusion

Nous avons discuté des moyens de résoudre le problème du pgcd pour deux nombres compris dans la plage [a,b]. C'est ainsi que nous pouvons résoudre le problème ci-dessus en C++ en utilisant différentes fonctions.

J'espère que vous avez trouvé cet article utile et clarifié tous vos concepts liés à ce problème.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!