C++实现找出正整数最小质因数的方法与代码解析

### 💡解题思路 要找出一个正整数 `n` 的最小质因数，可从最小的质数 2 开始，依次检查每个数是否是 `n` 的因数。若当前数是 `n` 的因数，且为质数（这里从 2 开始递增检查，遇到的第一个因数必然是质数），则该数就是最小质因数。 ### 🖥️代码实现 ```cpp #include <iostream> // 函数用于找出 n 的最小质因数 int findSmallestPrimeFactor(int n) { // 从 2 开始检查 for (int i = 2; i * i <= n; i++) { if (n % i == 0) { // 若 i 是 n 的因数，则 i 是最小质因数 return i; } } // 若 n 没有小于 sqrt(n) 的因数，则 n 本身是质数，最小质因数就是 n return n; } int main() { int n; std::cin >> n; int smallestPrimeFactor = findSmallestPrimeFactor(n); std::cout << smallestPrimeFactor << std::endl; return 0; } ``` ### 🔍代码解释 1. **`findSmallestPrimeFactor` 函数**： - 该函数接受一个整数 `n` 作为参数。 - 使用 `for` 循环从 2 开始检查到 `sqrt(n)`（通过 `i * i <= n` 实现）。 - 若 `n % i == 0`，说明 `i` 是 `n` 的因数，此时 `i` 就是最小质因数，返回 `i`。 - 若循环结束都未找到因数，说明 `n` 是质数，返回 `n` 本身。 2. **`main` 函数**： - 读取用户输入的整数 `n`。 - 调用 `findSmallestPrimeFactor` 函数得到最小质因数。 - 输出最小质因数。 ### ⚙️复杂度分析 - **时间复杂度**：$O(\sqrt{n})$，因为只需要检查到 `sqrt(n)`。 - **空间复杂度**：$O(1)$，只使用了常数级的额外空间。 ### 💡开发建议 - **边界条件处理**：虽然上述代码对于正整数输入能正常工作，但可添加输入验证，确保输入为正整数。例如： ```cpp int n; while (true) { std::cin >> n; if (n > 0) { break; } std::cout << "请输入一个正整数。" << std::endl; } ``` - **代码复用**：可将质因数检查等功能封装成独立函数，提高代码的复用性。 - **性能优化**：若需要处理大量输入，可预先计算一些质数表，减少重复计算。 ### 📚相关学习资源 - C++官方文档：https://en.cppreference.com/w/ - 《C++ Primer》：经典的 C++ 学习书籍，全面介绍 C++ 语言特性。 ######[AI写代码神器 | 738点数解答 | 2026-08-10 19:13:13]