資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 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 等）編寫相同的程式。我們希望您發現本文有所幫助。
更新於：2021-11-26
400 次檢視
廣告