En C++, traduisez ce qui suit en chinois : Comptez le nombre de nombres entre L et R qui sont premiers par rapport à P

Dans le monde de la programmation informatique, trouver le nombre de nombres dans une plage donnée qui sont premiers par rapport à un nombre spécifique peut être une tâche courante. Les nombres relativement premiers, également appelés nombres premiers relatifs, sont des nombres qui n'ont pas de facteur commun autre que 1. Dans cet article, nous explorerons la recherche du nombre de nombres relativement premiers par rapport à un nombre spécifique P entre les entiers donnés L et R en utilisant le langage C++.

Grammaire

Nous allons d'abord décrire la syntaxe des méthodes que nous utiliserons dans les exemples de code suivants -

int countCoprimes(int L, int R, int P);

Algorithme

L'algorithme que nous utiliserons pour calculer le nombre de nombres premiers entre eux est le suivant −

• Initialisez la variable count à 0, qui est utilisée pour stocker le nombre de nombres premiers entre eux.

• Itérez chaque numéro en commençant par L jusqu'à R.

• Pour chaque nombre, vérifiez s'il est relativement premier avec P.

• Si num et P sont relativement premiers, augmentez le nombre de 1.

• Renvoie la valeur finale du nombre.

Méthode 1 : Méthode naïve

La première méthode dont nous discuterons est la méthode naïve. Afin de vérifier la coprimité avec P à l'aide de l'algorithme d'Euclide, cette méthode nécessite de vérifier itérativement chaque nombre dans une plage spécifiée.

La traduction chinoise de

Exemple

est :

Exemple

#include <iostream>

int countCoprimes(int L, int R, int P) {
   int count = 0;
   for (int num = L; num <= R; num++) {
      int a = num;
      int b = P;
      while (b != 0) {
         int temp = b;
         b = a % b;
         a = temp;
      }
      if (a == 1)
         count++;
   }
   return count;
}

int main() {
   int L = 1; // Set the starting range value
   int R = 100; // Set the ending range value
   int P = 7; // Set the value of P
   
   int result = countCoprimes(L, R, P);
    
   std::cout << "Count of numbers between " << L << " and " << R << " coprime with " << P << ": " << result << std::endl;
   
   return 0;
}

Sortie

Count of numbers between 1 and 100 coprime with 7: 86

La traduction chinoise de

Explication

est :

Explication

La fonction countCoprimes accepte trois paramètres : L (valeur de plage de départ), R (valeur de plage de fin) et P (valeur de P).

Dans la fonction countCoprimes, nous initialisons une variable count à 0, qui stockera le nombre de coprimes.

La boucle for itère chaque numéro numérique de L à R.

Dans la boucle, on initialise les variables a et b à num et P respectivement.

Nous utilisons l'algorithme euclidien dans une boucle while pour trouver le plus grand diviseur commun (PGCD) de a et b en échangeant et en effectuant des opérations modulaires à plusieurs reprises.

Si GCD (stocké dans a) est égal à 1, cela signifie que num et P sont premiers entre eux. Dans ce cas, nous incrémentons la variable count.

Nous finalisons notre valeur de comptage en parcourant soigneusement tous les nombres et en la renvoyant une fois terminé.

Les fonctions principales attribuent judicieusement des valeurs appropriées aux variables L, R et P.

Nous appelons ensuite la fonction countCoprimes avec la valeur fournie et stockons le résultat dans la variable result.

Enfin, nous affichons le résultat, qui est le nombre de nombres entre L et R qui sont premiers par rapport à P.

Méthode 2 : Décomposition en facteur premier

Cette stratégie consiste à exploiter la factorisation première de P pour calculer avec précision le nombre d'entiers premiers entre eux compris entre L et R.

La traduction chinoise de

Exemple

est :

Exemple

#include <iostream>
#include <unordered_set>

int countCoprimes(int L, int R, int P) {
   std::unordered_set<int> factors;
   int tempP = P;

   for (int i = 2; i * i <= tempP; i++) {
      while (tempP % i == 0) {
         factors.insert(i);
         tempP /= i;
      }
   }

   if (tempP > 1)
      factors.insert(tempP);

   int count = 0;
   for (int num = L; num <= R; num++) {
      bool isCoprime = true;
      for (int factor : factors) {
         if (num % factor == 0) {
            isCoprime = false;
            break;
         }
      }
      if (isCoprime)
         count++;
   }

   return count;
}

int main() {
   int L = 1; // Set the starting range value
   int R = 100; // Set the ending range value
   int P = 7; // Set the value of P

   int result = countCoprimes(L, R, P);

   std::cout << "Count of numbers between " << L << " and " << R << " coprime with " << P << ": " << result << std::endl;

   return 0;
}

Sortie

Count of numbers between 1 and 100 coprime with 7: 86

La traduction chinoise de

Explication

est :

Explication

La fonction countCoprimes accepte trois paramètres : L (valeur de plage de départ), R (valeur de plage de fin) et P (valeur de P).

Nous créons un ensemble non ordonné de facteurs pour stocker les facteurs premiers de P. Nous initialisons une variable temporaire tempP à P.

Nous itérons de 2 à la racine carrée de tempP. Si tempP est divisible par i, nous ajoutons i à l'ensemble des facteurs et divisons tempP par i jusqu'à ce que tempP ne soit plus divisible par i.

Si tempP est supérieur à 1 après la boucle ci-dessus, cela signifie qu'il s'agit lui-même d'un nombre premier et qu'il doit être ajouté au facteur.

Nous initialisons la variable count à 0, qui stockera le nombre de nombres premiers entre eux.

Nous parcourons chaque nombre numérique de L à R et vérifions s'il est divisible par un facteur dans les facteurs définis. Si nous le pouvons, nous le qualifions de non-coprime.

Après avoir terminé l'itération de tous les nombres, le décompte résultant sera renvoyé comme valeur finale. Quant à la fonction main, elle initialise L, R et P avec les valeurs spécifiées.

Nous appelons ensuite la fonction countCoprimes avec la valeur fournie et stockons le résultat dans la variable result.

Enfin, nous affichons le résultat, qui est le nombre de nombres entre L et R qui sont premiers par rapport à P.

Conclusion

Calculer des nombres premiers entre eux dans une plage spécifiée L-R et satisfaire une valeur spécifique P est un bon défi pour les programmeurs - mais au niveau du code, quelle est la meilleure approche ? Dans le cadre de cet article, nous examinons en profondeur deux cas d’utilisation du C++ qui offrent une réelle efficacité lors de la résolution de problèmes comme celui-ci. Premièrement, en parcourant toutes les valeurs dans l'intervalle cible et en utilisant l'algorithme euclidien pour vérifier si les nombres correspondent en tant que nombres premiers entre eux, et également en utilisant la méthode de la fonction Euler, qui utilise une stratégie d'optimisation ; Quelle que soit la méthode que vous utilisez, la possibilité d'en tirer le meilleur parti dépend en grande partie de facteurs contextuels, tels que les nombres que vous choisissez et les intervalles que vous spécifiez, mais choisir judicieusement entre les deux méthodes possibles peut vraiment accélérer les choses dans l'ensemble. vitesse du programme. Pour les codeurs qui cherchent à ajouter des connaissances techniques à leurs compétences techniques et à leurs capacités créatives de résolution de problèmes, maîtriser le comptage de nombres premiers avec C++ grâce à ces méthodes peut être exactement ce dont ils ont besoin.

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!