SSOJ1186求完数
3738+
作者：crxis 发布：2018-05-19 分类：枚举
题目大意：完数是指因子（不含自己）之和等于他本身的数，请输出n以内所有完数。
题目描述
一个数如果恰好等于它的因子（能被它除尽的数，除本身）之和。比如6，它的因子有1,2,3,并且6=1+2+3，则6是完数。输出n以内所有完数。（n<10000）
输入
一行，一个整数n
输出
输出n以内的所有完数，每个数之间用空格隔开。
样例输入
1000
样例输出
6 28 496
解题思路
暴力解法：对于1到n中的每个数字i，分别枚举他们的约数，如何约数之和等于i，那么就是完数需要输出来。时间复杂度O(n*n)。
一个数的约数是成对存在的，一个不超过√n，另外一个不小于√n。我们只需要枚举小的那个约数，计算大的那个约数就行。需要特别注意的是，1和n这对约数，只加1，不加n；如果是平方数，如25，因子5只加1次。时间复杂度O(n√n)。
程序实现
