1 条题解
-
0
【本题解由站长编写】
试除法分解质因数:从 2 开始试到 √n,每找到一个因数就整除一次并记录。⚠️ 输出要去重:题目要的是「所有质因子」,重复的同一质因子只输出一次(实测 n=12 输出
2 3,不是2 2 3),所以每除尽后直接跳到下一个 d。剩下的 x > 1 是一个大于 √n 的质因子,补在末尾。代码(C++17)
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> fac; int x = n; for (int d = 2; (long long)d * d <= x; d++) { if (x % d == 0) { fac.push_back(d); while (x % d == 0) x /= d; // 除尽,保证质因子不重复输出 } } if (x > 1) fac.push_back(x); for (size_t i = 0; i < fac.size(); i++) { if (i) cout << " "; cout << fac[i]; } cout << endl; return 0; }
- 1
信息
- ID
- 4217
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者