使用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

上述程式碼的解釋

在這種方法中，我們遵循與埃拉托色尼篩相同的概念。我們找到 105 之前每個數字的除數。當我們收到 q 個查詢時，我們不需要找到除數，因此這大大降低了我們在詢問 q 個查詢時的時間複雜度。因此，我們的複雜度變成 O(Q*N)，其中 Q 是我們處理的查詢數量，N 是 n 的除數數量。

結論

在本文中，我們解決了一個問題：查詢列印 n 的所有約數，其中我們應用了埃拉托斯特尼篩選原理。我們也學習了解決此問題的 C 程序以及解決此問題的完整方法（Normal）。我們可以用其他語言像是C、java、python等語言來寫同樣的程式。我們希望這篇文章對您有幫助。

以上是使用C++列印出n的所有因數的查詢的詳細內容。更多資訊請關注PHP中文網其他相關文章！