Heim  >  Artikel  >  Backend-Entwicklung  >  Abfrage zum Ausdrucken aller Faktoren von n mit C++

Abfrage zum Ausdrucken aller Faktoren von n mit C++

PHPz
PHPznach vorne
2023-08-29 13:21:111428Durchsuche

Abfrage zum Ausdrucken aller Faktoren von n mit C++

In dem gegebenen Problem müssen wir alle Teiler einer gegebenen ganzen Zahl n drucken.

Input: 15
Output: 1 3 5 15
Explanation
Divisors of 15 are: 1,3, 5, 15

Input: 30
Output: 1 2 3 5 15 30

In der gegebenen Aufgabe können wir die in Sieve of Eratosthenes verwendete Methode anwenden, um alle Teiler von n zu finden.

Methoden, um die Lösung zu finden

In der angegebenen Methode wenden wir das Konzept des Siebes des Eratosthenes an und ermitteln die Teiler von n.

Beispiel

#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;

vector<int> divisors[100001]; // our vector containing number with all of its divisors
void findsieve(int max) { // filling data in vector divisors till 10e5
   for(int i = 1; i <= max; i++) {
      for(int j = i; j <= max; j += i)
         divisors[j].push_back(i);
   }
}
void __print(int n){ // the function to print divisors
   for(auto x : divisors[n])
      cout << x << " ";
   cout << "\n";
}

int main() {
   findsieve(100000); // we hardcode the sieve and divisors till 10e5
   int n = 6; // the given n
   __print(n);
   n = 30; // new n
   __print(n);
   return 0;
}

Ausgabe

1 2 3 6
1 2 3 5 6 10 15 30

Erklärung des obigen Codes

Bei dieser Methode folgen wir dem gleichen Konzept wie Sieve of Eratosthenes. Wir finden den Teiler jeder Zahl bis 105. Wir müssen den Divisor nicht finden, wenn wir q-Anfragen erhalten, was unsere Zeitkomplexität beim Stellen von q-Anfragen erheblich reduziert. Daher wird unsere Komplexität zu O(Q*N), wobei Q die Anzahl der von uns verarbeiteten Abfragen und N die Anzahl der Teiler von n ist.

Fazit

In diesem Artikel haben wir das Problem der Abfragedruckung aller Teiler von n gelöst, wobei wir das Sieb des Eratosthenes-Prinzips angewendet haben. Wir haben auch ein C++-Programm zur Lösung dieses Problems und eine vollständige Methode zur Lösung dieses Problems (Normal) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Wir hoffen, dass dieser Artikel für Sie hilfreich war.

Das obige ist der detaillierte Inhalt vonAbfrage zum Ausdrucken aller Faktoren von n mit C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Dieser Artikel ist reproduziert unter:tutorialspoint.com. Bei Verstößen wenden Sie sich bitte an admin@php.cn löschen