C++高效统计自然数因数个数的实现与优化

## 🔢 自然数因数个数求解 ### 💡 问题分析 给定自然数 n，统计其所有正因数的个数。因数指能整除 n 的正整数，且每个因数都是唯一的。 ### 📝 核心思路 最直接的方法是遍历从 1 到 n 的所有整数，检查是否能整除 n。时间复杂度 O(n)。对于较大的 n，可优化为遍历到 sqrt(n)，每找到一个因数，则对应配对因数也找到。 ### 💻 C++ 实现 ```cpp #include <iostream> using namespace std; int countFactors(int n) { int count = 0; for (int i = 1; i * i <= n; i++) { if (n % i == 0) { // i 是因数，且 i 与 n/i 不计入两个因数 if (i != n / i) { count += 2; } else { count += 1; // 平方数的情况，只计一次 } } } return count; } int main() { int n; cout << "请输入自然数 n: "; cin >> n; if (n <= 0) { cout << "请输入大于0的自然数" << endl; return 1; } int total = countFactors(n); cout << "total=" << total << endl; return 0; } ``` ### 🔍 代码说明 - 循环条件 `i * i <= n`，避免重复计数，且防止溢出。 - 当 `i` 是因数时，若 `i` 不等于 `n/i`，则一对因数（i 和 n/i）都计入，故加 2。 - 若 `i` 等于 `n/i`（即 n 是完全平方数），则只加 1。 - 示例：n=6，i=1 时加2（因数1,6），i=2 时加2（因数2,3），i=3 时 `3*3 > 6` 循环结束，total=4。 ### ⏱ 复杂度 时间复杂度 O(√n)，空间复杂度 O(1)。 ### 📊 测试示例 | n | 输出 | |---|------| | 6 | total=4 | | 12 | total=6 (1,2,3,4,6,12) | | 16 | total=5 (1,2,4,8,16) | | 1 | total=1 | ######[AI问答 | 568点数解答 | 2026-08-23 18:55:52]