Query to print out all factors of n using C++

In the given problem, we need to print all the divisors of a given integer n.

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 the given problem, we can apply the method used in the sieve of Eratosthenes to find all divisors of n.

Methods to find the solution

In the given method, we will apply the concept of Sieve of Eratosthenes and find the divisors of n.

Example

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

Output

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

Explanation of the above code

In this method we follow the same concept as Sieve of Eratosthenes . We find the divisor of every number up to 105. We don't need to find the divisor when we receive q queries, so this greatly reduces our time complexity when asking q queries. Therefore, our complexity becomes O(Q*N), where Q is the number of queries we process and N is the number of divisors of n.

Conclusion

In this article, we solved the problem of query printing all divisors of n, where we applied the Sieve of Eratosthenes principle. We also learned a C program to solve this problem and a complete method to solve this problem (Normal). We can write the same program in other languages ​​such as C, java, python and other languages. We hope this article was helpful to you.

The above is the detailed content of Query to print out all factors of n using C++. For more information, please follow other related articles on the PHP Chinese website!