使用 C++ 打印 n 的所有因数的查询

在给定的问题中，我们需要打印给定整数 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

在给定的问题中，我们可以应用埃拉托色尼筛法中用于查找 n 的所有因数的方法。

查找解决方案的方法

在给定的方法中，我们将应用埃拉托色尼筛法的基本概念并找到 n 的因数。

示例

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

输出

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

以上代码的解释

在这种方法中，我们遵循与埃拉托色尼筛法相同的概念。我们找到从 1 到 105 的每个数字的因数。当我们得到 q 个查询时，我们不需要找到因数，因此当要求 q 个查询时，这大大减少了我们的时间复杂度。因此，我们的复杂度变为 O(Q*N)，其中 Q 是我们处理的查询数量，N 是 n 的因数数量。

结论

在本文中，我们解决了一个问题：打印 n 的所有因数的查询，其中我们应用了埃拉托色尼筛法的原理。我们还学习了此问题的 C++ 程序以及我们解决此问题的完整方法（常规方法）。我们可以用其他语言（如 C、Java、Python 等）编写相同的程序。我们希望您发现本文有所帮助。

Prateek Jangid

更新于：2021-11-26

400 次查看

启动您的 职业生涯

通过完成课程获得认证

开始