Requête pour imprimer tous les facteurs de n en utilisant C++

Dans le problème donné, nous devons imprimer tous les diviseurs d'un entier n donné.

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

Dans le problème donné, nous pouvons appliquer la méthode utilisée dans Tamis d'Eratosthène pour trouver tous les diviseurs de n.

Méthodes pour trouver la solution

Dans la méthode donnée, nous appliquerons le concept de Tamis d'Eratosthène et trouverons les diviseurs de n.

Exemple

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

Sortie

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

Explication du code ci-dessus

Dans cette méthode, nous suivons le même concept que Sieve of Eratosthenes. Nous trouvons le diviseur de chaque nombre jusqu'à 105. Nous n'avons pas besoin de trouver le diviseur lorsque nous recevons q requêtes, cela réduit donc considérablement notre complexité temporelle lorsque nous posons q requêtes. Par conséquent, notre complexité devient O(Q*N), où Q est le nombre de requêtes que nous traitons et N est le nombre de diviseurs de n.

Conclusion

Dans cet article, nous avons résolu le problème de l'impression des requêtes de tous les diviseurs de n, où nous avons appliqué le principe du tamis d'Ératosthène. Nous avons également appris un programme C++ pour résoudre ce problème et une méthode complète pour résoudre ce problème (Normal). Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. Nous espérons que cet article vous a été utile.

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!