题目描述：
完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。
它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。
例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。s
输入n，请输出n以内(含n)完全数的个数。计算范围, 0 < n <= 500000
本题输入含有多组样例。
输入描述：
输入一个数字n
输出描述：
输出不超过n的完全数的个数
示例：
输入：
1000
7
100
输出：
3
1
2
解题思路：
本题有三个要点：
- 用a数组存放不同数字对应的完美数个数，比如7的完美数1,100的完美数为2，这两个完美数分别在7以内和7以后，那么数组中7-99的值为1,100的值为2,100到下一个完美数间所有的数都为2，依次累加。
- isPerfect函数分析是否为完美数。若是完美数，则该数在数组a中的值应为其前一个值加1；若不是完美数，则同前一个数一样。
- 在不同输入样例输入时，先判断a[num]是否为0，如果不为0，说明在前面的样例中计算过了，直接输出结果即可，可有效提速30%左右——36ms到26ms。
测试代码：
#include <iostream> #include <string> #include <vector> using namespace std; int a[500000]={0}; bool isPerfect(int number) { vector<int> result; result.push_back(1); for(int i=2;i<=number/2;++i) { if(number%i==0) result.push_back(i); } int sum=0; for(int it=0;it<result.size();++it) { sum+=result[it]; } if(sum==number) { a[number]=a[number-1]+1; return true; } else{ a[number]=a[number-1]; } return false; } int statistic(int number) { if(a[number]!=0) return a[number]; int size=0; for(int i=6;i<=number;++i) { if(isPerfect(i)) size++; } return size; } int main() { int number; while(cin>>number) { cout<<statistic(number)<<endl; } return 0; }
