原题链接: 求正整数2和n之间的完全数

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

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

  1. 理解完全数的定义:完全数是一个正整数,它等于其所有真因子(包括 1,但不包括自身)的和。例如,6 是一个完全数,因为 6 = 1 + 2 + 3。

  2. 输入输出:输入一个整数 n (n <= 5000),输出 2 到 n 之间的所有完全数,每行一个数,按从小到大的顺序排列。

  3. 解决方案

    • 首先,我们需要一个函数来判断一个数是否为完全数。
    • 然后,我们遍历从 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. 因数分解:为了求一个数的所有真因子,我们需要遍历从 1 到这个数平方根之间的所有整数。如果某个整数是这个数的因子,那么它的对应因子也可以求出。例如,12 的因子包括 1, 2, 3, 4, 6 和 12,我们只需遍历到 sqrt(12) 即可。

  2. 数据存储和排序:使用数组或列表来存储找到的完全数,并按顺序输出。

  3. 复杂度分析:由于我们需要遍历从 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})。如果 inum 的因子,我们将 inum / i 都加到因子和 sum 中。

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

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