Die Anzahl der Faktoren des Produkts von N Zahlen

Ein Teiler einer Zahl ist eine Zahl, die sie ohne Rest in ganze Zahlen teilen kann. Mit anderen Worten: Der Teiler einer Zahl n ist die Zahl, die n ergibt, wenn sie mit einer anderen ganzen Zahl multipliziert wird. Man kann ihn auch als Faktor einer Zahl bezeichnen.

Dividend ÷ Divisor = Quotient.

Wenn wir beispielsweise 5 durch 60 teilen, erhalten wir 12 und umgekehrt, daher können 12 und 60 als Teiler von 60 betrachtet werden.

Anzahl der Faktoren multipliziert mit N Zahlen

Die gegebene Aufgabe besteht darin, die Anzahl der Teiler des Produkts gegebener Zahlen zu ermitteln. Lassen Sie uns dieses Problem anhand eines Beispiels verstehen.

Angenommen, wir bekommen die Zahlen 6, 6 und 10. Das Produkt dieser Zahlen ist 120 und die Teiler von 120 sind 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120. Daher sollte die Ausgabe 16 sein.

Input: 6, 2, 10
Output: 16

Verwenden Sie den Modulo-Operator

Eine Möglichkeit, dies zu erreichen, besteht darin, den Modulo(%)-Operator zu verwenden, um die Teiler zu finden und sie zu zählen, indem von 1 bis Produkt iteriert wird.

Der Modulo-Operator (%)-Operator wird verwendet, um den Rest einer Divisionsoperation zu erhalten. Wenn der Rest einer Division Null ist, bedeutet dies, dass die Dividende durch den Divisor teilbar ist. Beispielsweise ist (30 % 5) 0, also ist 30 durch 5 teilbar.

Berechnen Sie die Anzahl der Teiler des Produkts aller Zahlen in einem Array.

• Multiplizieren Sie alle Zahlen im Array mit dem Multiplikationsoperator und speichern Sie das Ergebnis in einer Variablen mit dem Namen Produkt.

• Verwenden Sie den Modulo-Operator von 1 bis Produkt, dividieren Sie Produkt durch jede Zahl und erhalten Sie den Rest.

• Erstellen Sie eine Variablenanzahl. Wenn der Rest 0 ist, erhöhen Sie die Zählvariable.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Das folgende Programm berechnet die Anzahl der Teiler des Produkts einer gegebenen Zahl −

#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;
}

Ausgabe

Number of divisors: 40

Hinweis− Diese Methode ist für größere Zahlen sehr ineffizient. Da die Zahlen groß sind, wird auch das Produkt groß sein. Dies führt zu einer großen Anzahl von Iterationen und erhöht die zeitliche Komplexität.

Verwenden Sie die Primfaktorzerlegung

Wenn N eine zusammengesetzte Zahl ist, dann

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

Wobei a, b und c Primfaktoren sind, dann ergibt sich die Anzahl der Teiler von N durch die folgende Formel

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

Wir werden die oben genannten Konzepte verwenden, um die Teiler des Produkts von N Zahlen zu finden.

Algorithmus/Schritte

• Multiplizieren Sie alle N Zahlen und speichern Sie das Ergebnis in einer Variablen namens

  Produkt.

• Iterieren Sie eine for-Schleife von 2 bis zur Quadratwurzel,

  Produkt.

• Erhalten Sie die Hauptfaktoren des Produkts. Dazu verwenden wir den Modulo-Operator, um zu prüfen, ob

  Produkt durch den aktuellen Wert von x teilbar ist. Wenn möglich, wird x als Primfaktor und count als Potenz des Primfaktors gespeichert.

• Verwenden Sie die Bibliothek

  und die Funktion push_back(), um Primfaktoren und ihre Exponenten in den Vektorcontainern primeFactor und power zu speichern.

• Falls noch Primfaktoren übrig sind, speichern Sie diese ebenfalls.

• Berechnen Sie die Teiler, indem Sie von 0 bis zur Anzahl der Primfaktoren iterieren und die obige Formel verwenden.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Das Folgende ist ein Programm, um die Anzahl der Faktoren des Produkts einer gegebenen Zahl mithilfe der Primfaktorisierungsmethode zu ermitteln -

#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;
}

Ausgabe

Number of divisors: 40

Verwenden Sie verschachtelte Schleifen

Wir können das Produkt aller N Zahlen auch durch verschachtelte Schleifen ermitteln. In der äußeren Schleife müssen wir alle Zahlen von 1 bis

Produkt durchlaufen. Innerhalb dieses Zahlenbereichs finden wir alle möglichen Teiler. In der verschachtelten Schleife berechnen wir die Anzahl der Teiler für jede Zahl und ihre Vielfachen. Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#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;
}

Ausgabe

Number of divisors: 40

Fazit

Wir haben verschiedene Möglichkeiten besprochen, um die Anzahl der Teiler eines Produkts aus N Zahlen zu ermitteln, einschließlich der Verwendung des Modulo-Operators, der Primfaktorzerlegung, verschachtelter Schleifen und mehr. Für größere Zahlen können wir den Modulo-Operator nicht effizient verwenden. Um optimierte Ergebnisse zu erhalten, können wir Primfaktorzerlegung und verschachtelte Schleifen verwenden.

Das obige ist der detaillierte Inhalt vonDie Anzahl der Faktoren des Produkts von N Zahlen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!