# 菜鸟的coding · Day 013
求完全数
题目
小f帮助小草神纳西妲粉碎了大贤者和博士的阴谋，将她从净善宫中解救了出来。小草神和小f都听到了世界树中传来了一句断断续续的话，为了一探究竟，他们决定进入到世界树所在的空间中。但是由于禁忌知识的侵染，世界树所在的空间变得难以找到。
小草神通过一些方式找到了 n 个空间，世界树对空间的要求很独特——它需要这个空间的序号的所有因数之和恰好等于这个空间序号的两倍。小草神寻找到这 n 个空间就已经消耗了九成的力量，此时需要小f的帮助。而小f又双叒叕不会，就找到了你，希望你能帮帮他。作为感谢，小草神晚上会送你一场美梦。
输入：一个整数 n，表示空间区间为 [1, n]。
输出：每行一个整数，代表世界树可能存在的空间序号。
数据范围：n ≤ 10000。
样例：
输入
100
输出
6 28
思路
写 sumFactors 函数，枚举因子 c 到 √x：找到因子时，若 c*c==x 只加一次 c，否则 c 和 x/c 成对加入，避免重复。完全数条件即因数之和 = 2x，枚举 [1, n] 逐一判断输出。
#include<bits/stdc++.h>
using namespace std;
int sumFactors(int x){
int sum=0;
for(int c=1;c*c<=x;c++){
if(x%c==0){
if(c*c==x) sum+=c;
else sum+=c+x/c;
}
}
return sum;
}
int main(){
int n;
cin>>n;
for(int c=1;c<=n;c++){
if(sumFactors(c)==2*c){
cout<<c<<endl;
}
}
return 0;
}复杂度分析
- 时间复杂度：O(n · √n)，对每个数枚举因子到 √x。
- 空间复杂度：O(1)。
今日感受
枚举因子到 √x 时，找到 c 就能同时得到 x/c，效率翻倍。但要注意 c*c==x 时只能加一次，不然重复计算。还犯了一个小错：两个并列的 if 会都执行，导致完全数时多加了一次——改成嵌套 if/else 才能互斥。