alan23273850 的刷題筆記
d446: 生成因數
Tags: factor
出處：https://zerojudge.tw/ShowProblem?problemid=d446
提交：https://zerojudge.tw/Submissions?problemid=d446&account=allllllan123456
問題：請由小到大印出多個大於 1 的 int 的所有正因數。
解法：這題比較建議的作法便是先求出一個整數的標準分解式，再用 DFS 分別求出每個質數在不同的可行個數底下的乘積所形成的因數是多少，排序之後再印出來。這題也不用建質數表。
1#include <bits/stdc++.h>
2using namespace std;
3
4// 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 6469693230 > 2147483647.
5int arr[9], arr2[9], arrL;
6vector<int> ans;
7
8void dfs(int layer, int num) {
9 if (layer == arrL) {
10 ans.push_back(num);
11 return;
12 }
13 int t = 1;
14 for (int i=arr2[layer]; i>=0; i--)
15 dfs(layer+1, num * t),
16 t *= arr[layer];
17}
18
19int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
20 int n;
21 while (cin >> n) { ans.clear();
22 int cnt=0, p=2; arrL=0;
23 while (true)
24 if (n % p) {
25 if (cnt) arr[arrL] = p, arr2[arrL++] = cnt;
26 p++; cnt = 0;
27 if (n == 1) break;
28 if (p > sqrt(n)) p = n;
29 } else n /= p, cnt++;
30 dfs(0, 1);
31 sort(ans.begin(), ans.end());
32 for (int i=0; i<ans.size(); i++)
33 cout << ans[i] << ' ';
34 cout << '\n';
35 }
36 return 0;
37}