求出1…n之间的所有亲和数
所谓亲和数，即存在数a和数b，a的所有真因子之和等于b，b的所有真因子之和等于a，则称a和b为一对亲和数。
例如220的真因子为：1、2、4、5、10、11、20、22、44、55、110，和为284；而284的真因子为：1、2、4、71、142，和正好为220。故220和284是一对亲和数。
分析：一眼看去很难，似乎需要将所有（1-n）的数的因子求出，然后相加求和，组后比较值与真因子是否形同，那么这中做法不管是空间还是时间的复杂度都难以想象。本人通过百度，看到一个伴随数组，即利用数组的下标与值的关系解决一些看似复杂的问题。现在设j 的真因子的和为sum[j],又要求sum[j]的真因子和为 j，（如果j和sum[j]是亲和数的话），所以可以先求出1-n这些数的对应的真因子的和sum[],然后比较j和sum[sum[j]]即可；
代码如下：
// [10/7/2013 qingezha] 求出1…n之间的所有亲和数。//所谓亲和数，即存在数a和数b，a的所有真因子之和等于b，b的所有真因子之和等于a，则称a和b为一对亲和数。//例如220的真因子为：1、2、4、5、10、11、20、22、44、55、110，和为284；而284的真因子为：1、2、4、71、142，和正好为220。故220和284是一对亲和数。//现在设j 的真因子和为sum[j],那么j 可以被所有的因子整除的和为sum[j] ,其中可以整除就是关键void print_Affsum(int n){if(n<=0) return;int *sum = new int[n+1];for (int i=1;i<n+1;++i) sum[i]=1;//所有亲和数都有因子 1for (int i=2;i<n/2;++i)//i 作为因子,所以最大也只能为 n/2{for (int j=2*i;j<n+1;j+=i)//j 为可以整除 i，所以递增为 i{sum[j] += i;}}int i = 1;while(i<n+1){if(sum[i]<n+1&&i==sum[sum[i]])//这里别忘记检测sum[i]的值，因为sum[sum[i]]可能越界cout<<i<<" "<<sum[i]<<endl;++i;}delete[] sum;}