描述 所谓完数是指一个数恰好等于它的因子之和（不包含本身）。比如6的因子为1、2、3，而6=1+2+3，所以6是完数。 格式 输入格式 输入n，n表示在1~n之间有多少完数。 输出格式 输出在1~n之间有多少完数。 样例 输入样例 100 输出样例 2

算法1

暴力枚举

对于每个数，枚举其因子，并求和，判断是否等于该数本身。

时间复杂度

枚举每个数的因子需要 O(nlogn) 的时间，总时间复杂度为 O(n^2logn)。

C++ 代码

算法2

优化枚举

对于每个数，枚举其因子时只需要枚举到 $\sqrt{n}$ 就可以了，因为大于 $\sqrt{n}$ 的因子一定是小于 $\sqrt{n}$ 的因子的倒数。

时间复杂度

枚举每个数的因子需要 O(根号n) 的时间，总时间复杂度为 O(nlogn)。

C++ 代码

相关问题

用C语言 实现求1000之内的所有完数，所谓完数是指一个数恰好等于它所有因子之和。

#include <stdio.h>

int main()
{
int i, j, sum;

for (i = 1; i <= 1000; i++) {
sum = 0;
for (j = 1; j < i; j++) {
if (i % j == 0) {
sum += j;
}
}
if (sum == i) {
printf("%d是完数，因子有：", i);
for (j = 1; j < i; j++) {
if (i % j == 0) {
printf("%d ", j);
}
}
printf("\n");
}
}

return 0;
}

C语言完数 试题操作 查看部分测 描述 提交代码 所谓完数是指一个数恰好等于它的因子 查看提交证 之和（不包含本身）。比如6的因子为 得分： 1、2、3，而6=1+2+3，所以6是完 数。 结果： 格式 输入格式 输入n，n表示在1~n之间有多少完数 输出格式 输出在1-n之间有多少完数。

答案：

以下是 C 语言的代码实现：

#include <stdio.h>

int main() {
int n, i, j, sum;
scanf("%d", &n);
int count = 0;
for (i = 1; i <= n; i++) {
sum = 0;
for (j = 1; j < i; j++) {
if (i % j == 0) {
sum += j;
}
}
if (sum == i) {
count++;
}
}
printf("%d", count);
return 0;
}

这段代码可以计算在 1~n 之间有多少个完数。