C++ 实现输出指定范围内非3倍数数字的因数

好的，我们一起来解决这个问题。 --- ## 🎯 题目理解 我们需要输出从 `a` 到 `b`（包含两端）范围内所有数字的因数，但有以下**特殊规则**： - 如果某个数字是 **3 的倍数**，则**跳过**该数字，不输出它的因数。 - 每个数字的因数按**升序**输出，在同一行内，用**空格**分隔。 - 每个数字的因数占一行。 例如输入 `10 15`： - 10不是3的倍数，输出其因数：`1 2 5 10` - 11不是3的倍数，输出：`1 11` - 12是3的倍数，跳过 - 13不是3的倍数，输出：`1 13` - 14不是3的倍数，输出：`1 2 7 14` - 15是3的倍数，跳过 --- ## 🧠 核心思路 1. **遍历**从 `a` 到 `b` 的每个整数 `i`。 2. 如果 `i % 3 == 0`，则**跳过**，继续下一个。 3. 否则，找出 `i` 的所有因数： - 一个数 `i` 的因数就是所有能整除 `i` 的数，即 `j` 从 `1` 到 `i`，若 `i % j == 0`，则 `j` 是因数。 - **优化**：因数成对出现，`j` 只遍历到 `sqrt(i)`，然后同时添加 `i / j`（注意去重和排序）。 4. 将因数按**升序**输出，并在每个数输出完毕后换行。 --- ## 💻 C++ 实现 ```cpp #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; // 获取一个数的所有因数（升序） vector<int> getFactors(int n) { vector<int> factors; int limit = sqrt(n); for (int i = 1; i <= limit; ++i) { if (n % i == 0) { factors.push_back(i); if (i != n / i) { factors.push_back(n / i); } } } sort(factors.begin(), factors.end()); return factors; } int main() { int a, b; cin >> a >> b; for (int num = a; num <= b; ++num) { // 特殊规则：3的倍数跳过 if (num % 3 == 0) { continue; } vector<int> factors = getFactors(num); for (size_t i = 0; i < factors.size(); ++i) { if (i > 0) cout << " "; cout << factors[i]; } cout << endl; } return 0; } ``` --- ## 📌 代码说明 | 部分 | 解释 | |------|------| | `sqrt(n)` | 用于减少循环次数，提高效率 | | `factors.push_back(i)` | 添加一个小因数 | | `if (i != n / i)` | 防止平方数重复添加 | | `sort(factors.begin(), factors.end())` | 确保输出有序 | | `if (num % 3 == 0) continue` | 实现特殊规则 | --- ## ⏱ 时间与空间复杂度 - **时间复杂度**：O((b-a+1) × √b)，对于 `b` 最大为 10^6 级别的场景依然较快。 - **空间复杂度**：O(√b)，用于存储临时因数列表，每次输出后即释放。 --- ## 💡 开发建议 1. **输入验证**：确保 `a <= b`，并考虑 `a` 可能为负数或 0 的情况（题目要求正整数因数）。 2. **边界情况**：若 `a` 到 `b` 范围内所有数都是 3 的倍数，则输出为空，程序逻辑上仍需正确处理。 3. **性能优化**：如果多次查询，可先预处理因数表，但本题单次查询，无需过度优化。 4. **输出格式**：注意最后一行也要输出换行，避免出现格式错误。 5. **C++ 特性**：使用 `sqrt` 需要包含 `<cmath>`，使用 `vector` 和 `sort` 需包含相应头文件。 --- ## ❓ 常见问题 (FAQ) **Q1：如果 a 或 b 是负数怎么办？** A：题目未明确说明，但因数通常针对正整数。如果出现负数，可以取绝对值处理。 **Q2：如何避免因数重复输出？** A：使用 `if (i != n / i)` 判断，或者最后再 `unique`。 **Q3：为什么用 `sqrt` 优化？** A：因为因数成对出现，遍历到平方根即可找到所有因数，将复杂度从 O(n) 降到 O(√n)。 --- ######[AI写代码神器 | 1115点数解答 | 2026-07-24 21:20:11]