题目描述
求100000000之内的完全数。
样例
无
今天这道题超时了，我和爸爸一起分析了一下：
算法1
(暴力枚举) (O(n^2))
int sum=0;
for(int i=2;i<=n;i++)
for(int j=2;j<i;j++)
if(i%j==0) sum+=j;
if(sum==n){
printf("%d is perfect
",x);
}else{
printf("%d is not perfect
",x);
}
这个最基本的办法超时了，TLE！！！~~~
爸爸帮我分析了一下，我总结是这样的：
1、一次算一个因子，导致它慢。
因为一个数如果能被自己的一个因子整除，那么整除的结果，就是另一个因子，应该在循环写成(x/i),我们可以测试一个数是因子的时候，一下子获取到两个因子，这样就会快一些。
2、一下子保存两个因子，会造成数量重复
以(12)为例，(2 imes 6)，(3 imes 4)都是没有问题的，但(4 imes 3),(6 imes 2)也会加到(sum)里去，就明显就重复了，肯定不行。爸爸的办法很有意思，他要求每对因子，前面的要小于后面的（这里面还有一个等于的问题，我一会再讲），如果前面的大于后面的就不能要的，防止重复。用语句表达就是 (i<x/i),这里面的(for)循环的执行限制条件居然还可以是变化的，真是挺有意思的。
一下子找两个因子，还有另一个好处，就是(12)，我们找到(3)的时候，就不用再去找(4)了，因为那样就重复了，数据的上限小了，就会更快。
for(int i = 2; i<= x/i; i++){
if (x % i == 0) {
s+=i;
s+=x/i;
}
}
3、为什么要有等号呢？
是因为有些数有同时需要两个因子相等的，比如(16)，(25)，(36)这样的完全平方数，可以拆分为(4 imes 4),(5 imes 5),(6 imes 6)，也就是存在两个一样的因子，如果没有那个等号，就丢失了一个因子，就不符合要求了。但我发现就算是不打等号，也是可以(AC)的，爸爸告诉我说，那是因为没有一个完全平方数是完全数，所以造成结果是一样的，我问是不是如果数字无限大，可能会有完全数是完全平方数，这个爸爸也不懂了，说需要数学家去证明，不知道。
4、为什么是while(n--) ？
是因为一共n个数字需要检查，每检查一个n就减少一个，就像是火箭发射一样，5,4,......1 发射！！！！！
5、为什么要在输出那里写成 if(s==x && x>1) 呢？
s==x是啥我就不说了，x>1是因为任何数都有1这个因子，我们不讨论它，而且最小的完全数是6，如果输入的是1肯定不是完全数
完整的代码：
#include <iostream>
using namespace std;
int main()
{
int n;
cin>>n;
while (n--)
{
int x;
int s=1;
cin>>x;
for(int i = 2; i<= x/i; i++){
if (x % i == 0) {
s+=i;
s+=x/i;
}
}
if(s==x && x>1)
printf("%d is perfect
",x);
else
printf("%d is not perfect
",x);
}
return 0;
}