信息奥赛一本通函数题库解析: 求正整数2和n之间的完全数

根据题目描述和样例输入输出的要求，我们需要编写一个程序，找到 2 和 n 之间的完全数，并按升序输出。一个完全数是指它的所有真因子（不包括自身）之和等于它本身。

以下是针对这道题的详细解题思路：

理解完全数的定义：完全数是一个正整数，它等于其所有真因子（包括 1，但不包括自身）的和。例如，6 是一个完全数，因为 6 = 1 + 2 + 3。
输入输出：输入一个整数 n (n <= 5000)，输出 2 到 n 之间的所有完全数，每行一个数，按从小到大的顺序排列。
解决方案：
- 首先，我们需要一个函数来判断一个数是否为完全数。
- 然后，我们遍历从 2 到 n 的所有整数，使用该函数判断是否为完全数。
- 如果是完全数，将其存储在一个列表中。
- 最后，按顺序输出列表中的所有完全数。

以下是实现该方案的代码：

#include <iostream>
using namespace std;

// 函数：判断一个数是否为完全数
bool is_perfect(int num) {
    if (num == 1) {
        return false; // 1 不是完全数
    }
    int sum = 1; // 1 是所有数的因子
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            sum += i;
            if (i * i != num) { // 避免重复添加平方根
                sum += num / i;
            }
        }
    }
    return sum == num; // 如果因子和等于自身，则是完全数
}

int main() {
    int n;
    cin >> n; // 读入 n

    int perfect_numbers[5]; // 假设最多有 5 个完全数
    int count = 0; // 完全数的计数

    for (int i = 2; i <= n && count < 5; ++i) {
        if (is_perfect(i)) {
            perfect_numbers[count++] = i; // 如果 i 是完全数，加入数组
        }
    }

    for (int i = 0; i < count; ++i) {
        cout << perfect_numbers[i] << endl; // 输出所有的完全数
    }

    return 0;
}

知识点总结：

因数分解：为了求一个数的所有真因子，我们需要遍历从 1 到这个数平方根之间的所有整数。如果某个整数是这个数的因子，那么它的对应因子也可以求出。例如，12 的因子包括 1, 2, 3, 4, 6 和 12，我们只需遍历到 sqrt(12) 即可。
数据存储和排序：使用数组或列表来存储找到的完全数，并按顺序输出。
复杂度分析：由于我们需要遍历从 2 到 n 的所有数，并对每个数进行因数分解，时间复杂度为 O(n * sqrt(n))，对于 n <= 5000 是可以接受的。

这段代码可以有效解决这个问题，找出所有满足条件的完全数并输出。

为什么只需遍历到 sqrt(12) 即可

只需遍历到 (\sqrt{n}) 是因为在查找一个数 (n) 的因子时，如果 (i) 是 (n) 的一个因子，那么 (\frac{n}{i}) 也是 (n) 的一个因子。具体来说，如果我们找到一个因子 (i)，那么我们可以直接确定另一个因子 (\frac{n}{i})。

例如，对于 (n = 12)：

因子对包括 (1, 12), (2, 6), 和 (3, 4)。
如果我们从 1 遍历到 (\sqrt{12} \approx 3.46)，那么当我们找到因子 2 时，我们也可以确定 6 是因子（因为 (12 / 2 = 6)）。
同样，当我们找到因子 3 时，我们也可以确定 4 是因子（因为 (12 / 3 = 4)）。

这就意味着，我们只需遍历到 (\sqrt{n}) 就可以找到所有的因子对，因为对于每一个 (i \leq \sqrt{n})，对应的 (\frac{n}{i}) 都会被找到。

这个方法大大减少了需要检查的数的数量，降低了时间复杂度。遍历到 (\sqrt{n}) 的时间复杂度是 (O(\sqrt{n}))，而不是遍历到 (n) 的 (O(n))，这对于较大的 (n) 来说是非常有效的。

让我们再来看一遍代码中的这部分：

for (int i = 2; i * i <= num; ++i) {
    if (num % i == 0) {
        sum += i;
        if (i * i != num) { // 避免重复添加平方根
            sum += num / i;
        }
    }
}

这里的 i * i <= num 就是为了遍历到 (\sqrt{num})。如果 i 是 num 的因子，我们将 i 和 num / i 都加到因子和 sum 中。

避免重复添加平方根的目的是处理完全平方数的情况。例如，16 的因子包括 1, 2, 4, 8 和 16，但我们不希望将 4 添加两次。

通过这种方法，我们能够高效地找到所有因子并判断一个数是否为完全数。

知识点总结：

为什么 只需遍历到 sqrt(12) 即可

为什么只需遍历到 sqrt(12) 即可