Le nombre de facteurs du produit de N nombres

Le diviseur d'un nombre est un nombre qui peut le diviser en entiers sans aucun reste. En d’autres termes, le diviseur d’un nombre n est le nombre qui donne n lorsqu’il est multiplié par tout autre nombre entier. On peut aussi l'appeler facteur d'un nombre.

Dividend ÷ Divisor = Quotient.

Par exemple, si l'on divise 5 par 60, nous obtiendrons 12 et vice versa, donc 12 et 60 peuvent être considérés comme des diviseurs de 60.

Nombre de facteurs multiplié par N nombres

La tâche confiée est de trouver le nombre de diviseurs du produit de nombres donnés. Comprenons ce problème à travers un exemple.

Supposons que l'on nous donne les nombres 6, 6 et 10. Le produit de ces nombres est 120 et les diviseurs de 120 sont 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120. Par conséquent, le résultat devrait être 16.

Input: 6, 2, 10
Output: 16

Utilisez l'opérateur modulo

Une façon d'y parvenir est d'utiliser l'opérateur modulo(%) pour trouver les diviseurs et les compter en itérant de 1 à produit.

L'opérateur modulo (%) est utilisé pour obtenir le reste d'une opération de division. Si le reste d'une division est nul, cela signifie que le dividende est divisible par le diviseur. Par exemple, (30 % 5) vaut 0, donc 30 est divisible par 5.

Calculez le nombre de diviseurs du produit de tous les nombres d'un tableau.

• Multipliez tous les nombres du tableau à l'aide de l'opérateur multiplication et stockez le résultat dans une variable nommée produit.

• Utilisez l'opérateur modulo, de 1 à Produit, divisez Produit par chaque nombre et obtenez le reste.

• Créez un nombre de variables, et si le reste est 0, incrémentez la variable de nombre.

La traduction chinoise de

Exemple

est :

Exemple

Le programme suivant calcule le nombre de diviseurs du produit d'un nombre donné −

#include <iostream>
using namespace std;

// Define a function for finding the number
int findNumberOfDivisors(int arr[], int N) {

   // Multiply all the numbers in the array
   int product = 1;
   for (int x = 0; x < N; x++) {
      product *= arr[x];
   }

   // Count the divisors
   int count = 0;
   for (int x = 1; x <= product; x++) {
      if (product % x == 0) {
         count++;
      }
   }

   return count;
}
int main() {

   // Declaration of the numbers and N
   int numbers[] = { 12, 16, 40 };
   int N = sizeof(numbers) / sizeof(numbers[0]);
   int divisors = findNumberOfDivisors(numbers, N);
   std::cout << "Number of divisors: " << divisors;
   return 0;
}

Sortie

Number of divisors: 40

Remarque− Cette méthode est très inefficace pour les grands nombres. Puisque les chiffres sont grands, le produit sera également grand. Cela entraînera un grand nombre d’itérations, augmentant ainsi la complexité temporelle.

Utilisez la factorisation première

Si N est un nombre composé, alors

N = x<sup>a</sup>  * y<sup>b</sup>  * z<sup>c</sup>

Où a, b et c sont des facteurs premiers, alors le nombre de diviseurs de N est donné par la formule suivante

(a + 1)(b + 1)(c + 1)

Nous utiliserons les concepts ci-dessus pour trouver les diviseurs du produit de N nombres.

Algorithme/Étapes

• Multipliez tous les N nombres et stockez le résultat dans une variable appelée produit.

• Itérer une boucle for de 2 jusqu'à la racine carrée, product.

• Obtenez les facteurs premiers du produit. Pour ce faire, nous utilisons l'opérateur modulo pour vérifier si produit est divisible par la valeur actuelle de x. Si possible, x est stocké comme facteur premier et count est stocké comme puissance du facteur premier.

• Utilisez la bibliothèque et la fonction push_back() pour stocker les facteurs premiers et leurs exposants dans des conteneurs vectoriels primeFactor et power.

• S'il reste des facteurs premiers, stockez-les également.

• Calculez le diviseur en itérant de 0 au nombre de facteurs premiers et en utilisant la formule ci-dessus.

La traduction chinoise de

Exemple

est :

Exemple

Ce qui suit est un programme pour trouver le nombre de facteurs du produit d'un nombre donné en utilisant la méthode de factorisation première -

#include <iostream>
#include <vector>
#include <cmath>

// Multiply all the N numbers
int findNumberOfDivisors(int arr[], int N) {
   int product = 1;
   for (int x = 0; x < N; x++) {
      product *= arr[x];
   }

   std::vector<int> primeFactor;
   std::vector<int> power;
    
   // Check if x is divisor of product

   // Store the prime factor and exponent in the vector container
   for (int x = 2; x <= sqrt(product); x++) {
      if (product % x == 0) {
         int count = 0;
         while (product % x == 0) {
            product /= x;
            count++;
         }
         primeFactor.push_back(x);
         power.push_back(count);
      }
   }
    
   // Store the remaining prime factor (if present)  
   if (product > 1) {
      primeFactor.push_back(product);
      power.push_back(1);
   }
    
   // Count the number of divisors
   int divisorsCount = 1;
   for (int x = 0; x < primeFactor.size(); x++) {
      divisorsCount *= (power[x] + 1);
   }

   return divisorsCount;
}

int main() {
   int numbers[] = {12, 16, 40};
   
   // Calculate the number of elements in the array
   int N = sizeof(numbers) / sizeof(numbers[0]);
   int divisors = findNumberOfDivisors(numbers, N);
   std::cout << "Number of divisors: " << divisors << std::endl;
   return 0;
}

Sortie

Number of divisors: 40

Utilisez des boucles imbriquées

Nous pouvons également trouver le produit de tous les nombres N via des boucles imbriquées. Dans la boucle externe, nous devons parcourir tous les nombres de 1 à produit. Dans cette plage de nombres, nous trouverons tous les diviseurs possibles. Dans la boucle imbriquée, nous calculerons le nombre de diviseurs pour chaque nombre et ses multiples.

La traduction chinoise de

Exemple

est :

Exemple

#include <iostream>
#include <vector>

int findNumberOfDivisors(int arr[], int N) {
   std::vector<int> divisorsCount(11000, 0);
    
   // Multiply all the N numbers
   int product = 1;
   for (int x = 0; x < N; x++) {
      product *= arr[x];
    }
    
   // Count of divisors
   for (int x = 1; x <= product; x++) {
      for (int y = x; y <= product; y += x) {
         divisorsCount[y]++;
      }
   }

   return divisorsCount[product];
}

int main() {
   int numbers[] = {12, 16, 40};
   int N = sizeof(numbers) / sizeof(numbers[0]);
   int divisors = findNumberOfDivisors(numbers, N);
   std::cout << "Number of divisors: " << divisors << std::endl;
   return 0;
}

Sortie

Number of divisors: 40

Conclusion

Nous avons discuté de différentes façons de trouver le nombre de diviseurs d'un produit de N nombres, notamment en utilisant l'opérateur modulo, la factorisation première, les boucles imbriquées, etc. Pour des nombres plus grands, nous ne pouvons pas utiliser efficacement l’opérateur modulo. Afin d'obtenir des résultats optimisés, nous pouvons utiliser la factorisation première et les boucles imbriquées.

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!