信息奥赛一本通函数题库解析: 求正整数2和n之间的完全数
原题链接: 求正整数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 添加两次。
通过这种方法,我们能够高效地找到所有因子并判断一个数是否为完全数。