知識概覽

• 試除法求一個數(shù)的約數(shù)的時間復(fù)雜度是。

例題展示

題目鏈接

活動 - AcWing 系統(tǒng)講解常用算法與數(shù)據(jù)結(jié)構(gòu)，給出相應(yīng)代碼模板，并會布置、講解相應(yīng)的基礎(chǔ)算法題目。https://www.acwing.com/problem/content/871/

題解

用試除法求約數(shù)，總的時間復(fù)雜度是，也就是400萬~500萬之間。

代碼

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;vector<int> get_divisors(int n)
{vector<int> res;for (int i = 1; i <= n / i; i++)if (n % i == 0){res.push_back(i);if (i != n / i) res.push_back(n / i);}sort(res.begin(), res.end());return res;
}int main()
{int n;cin >> n;while (n--){int x;cin >> x;auto res = get_divisors(x);for (auto t : res) cout << t << ' ';cout << endl;}return 0;
}

參考資料

1. AcWing算法基礎(chǔ)課