使用 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
在给定的问题中，我们可以应用Eratosthenes筛法中使用的方法来找到n的所有因数。
寻找解决方案的方法
在给定的方法中，我们将应用Eratosthenes筛法所基于的概念并找到n的因数。
示例
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
vector<int> divisors[100001]; //我们的向量包含数字及其所有除数
void findsieve(int max) { //以向量除数填充数据直到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){ //打印除数的函数
for(auto x : divisors[n])
cout << x << " ";
cout << "\n";
}
int main() {
findsieve(100000); //我们将筛子和除数硬编码到10e5
int n = 6; //给定的n
__print(n);
n = 30; //新的
__print(n);
return 0;
}输出结果1 2 3 6 1 2 3 5 6 10 15 30
上面代码的解释
在这种方法中，我们遵循与埃拉托色尼筛法相同的概念。我们找到每个数的除数直到105。当我们得到q个查询时，我们不需要找到除数，所以这大大降低了我们在查询q个查询时的时间复杂度。因此，我们的复杂度变为O(Q*N)，其中Q是我们处理的查询数量，N是n的除数。
结论
在本文中，我们解决了一个问题：查询打印n的所有除数，其中我们应用了Eratosthenes的筛分原理。我们还学习了针对此问题的C++程序以及解决此问题的完整方法(Normal)。我们可以用其他语言编写相同的程序，例如C、java、python和其他语言。我们希望这篇文章对您有所帮助。