Le plus petit entier qui divise chaque élément d'un tableau donné > 1 : en utilisant C++

Dans cet article, on nous donne un tableau d'entiers et nous devons trouver le plus petit nombre supérieur à 1 qui divise tous les éléments du tableau. Par exemple, considérons un exemple de tableau [30, 90, 15, 45, 165].

vector<int> arr = {30, 90, 15, 45, 165};
result = solve(arr);

Nous pouvons maintenant trouver le plus grand diviseur commun (PGCD) des tableaux. Si le résultat est 1, ce qui signifie que seul 1 peut diviser l'ensemble du tableau, nous pouvons renvoyer -1 ou "Pas possible". Si le résultat est un entier, alors cet entier divise le tableau entier. Cependant, cet entier ne peut pas être le plus petit entier qui divise l’ensemble du tableau. Il est intéressant de noter que les facteurs de cet entier divisent également l’ensemble du tableau, ce qui est logique. Ainsi, si nous pouvons trouver le plus petit facteur de cet entier (PGCD), nous avons le plus petit entier qui divise le tableau entier. Donc, en bref, nous devons trouver le plus grand diviseur commun (PGCD) des tableaux, puis le plus petit facteur est notre réponse.

La traduction chinoise de

Exemple

est :

Exemple

Le code C++ suivant peut trouver un plus petit entier supérieur à 1 qui peut diviser tous les éléments du tableau. Ceci peut être réalisé en trouvant le plus grand diviseur commun d'une liste d'éléments -

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int divisor(int x) {
   if (x%2 == 0) {
      return 2;
   }
   for (int i=3;i*i<=x;i+=2) {
      if (x%i == 0) {
         return i;
      }
   }
   return x;
}
int solve(vector<int> arr) {
   int gcd = 0;
   for (int i=0;i<arr.size();i++) {
      gcd = __gcd(gcd, arr[i]);
   }
   return divisor(gcd);
}
int main() {
   vector<int> arr = {30, 90, 15, 45, 165};
   cout << solve(arr);
   return 0;
}

Sortie

3

La traduction chinoise de

Exemple

est :

Exemple

S'il y a de nombreuses requêtes, la recherche des facteurs premiers d'un nombre sera répétée. En utilisant la méthode du tamis, nous pouvons calculer les facteurs premiers d’un nombre.

En C++, une autre méthode d'implémentation pour trouver le plus petit nombre supérieur à 1 est la suivante :

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 100005;
vector<int> prime(MAX, 0);
void sieve() {
   prime[0] = 1;
   prime[1] = -1;
   for (int i=2; i*i<MAX;i++) {
      if (prime[i] == 0) {
         for (int j=i*2;j<MAX;j+=i) {
            if (prime[j] == 0) {
               prime[j] = i;
            }
         }
      }
   }
   for (int i=2; i<MAX;i++) {
      if (!prime[i]) {
         prime[i] = i;
      }
   }
}
int solve(vector<int> arr) {
   int gcd = 0;
   for (int i=0; i<arr.size();i++) {
      gcd = __gcd(gcd, arr[i]);
   }
   return prime[gcd];
}
int main() {
   sieve();
   vector<int> arr = { 30, 90, 15, 45, 165 };
   cout << solve(arr);
   return 0;
}

Sortie

3

Conclusion

Nous avons utilisé la méthode sqrt(n) pour obtenir le facteur minimum. Cela peut être optimisé, je vous laisse essayer. La complexité temporelle est O(sqrt(n)). Dans la deuxième méthode, la complexité temporelle sera celle de la méthode tamis, qui est O(nlog(log(n))). Notez que nous pouvons trouver la limite supérieure de la méthode tamis en fonction de la variable globale MAX que nous avons définie.

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!