在给定的问题中,我们需要打印给定整数 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 和其他语言。我们希望这篇文章对您有所帮助。