时间效率题

解题思路:

1、最菜鸟的解题方法：就是遍历使用双层for把两个数遍历出来，然后在里面调用一个函数，函数的用途是判断这两个数是否是亲密数，函数参数是遍历的两个数。然后函数体定义部分是，使用for循环把这两个数的因子和各种求出了，再写一个判断即可。这样的话，结果是对的，但是时间超限。

2、普通解法：使用一个数组存放3000个数的因子和，然后与3000个数本身比较，没有什么难的

3、最优解：在求3000个数的因子和时，这个地方可以在优化一下，因为当一个数是另一个数的n倍时，这会重复计算某些数的因子和。举个例子，a = 4，b = 12。a的因子和时1+2，b的因子和时1+2+3+4+6。这是不是重复算了一下。当然这些数比较小的时候，影响不大，但是当数大的时候，就显得这一步尤为重要了（只不过我还没有写出来最优的，等写出来会更新的）

注意事项：

本题用是是普通解法。创建一个数组来存放它们的1因子和，用它们自身做下标，这样后面就方便用。求因子和应该没什么问题，最后的逻辑判断可能存在一些问题。使用1个for循环把那个数组遍历出来，然后里面嵌套一个for循环，把3000个数遍历出来，一定记得亲密数是两个数的因子和等于对方本身。

参考代码:

#include <stdio.h>
int main()
{
    int factor[3000] = {0};//为了存放因子和
    int i,j;//循环用
    for(i = 2;i < 3000;i++)
    {
        for(j = 1;j <= i / 2;j++)//不必遍历完，到一半就行
        {
            if(i % j == 0)
                factor[i] += j;
        }
    }
    for(i = 0;i < 3000;i++)
    {
        for(j = 2999;j > i;j--)//j倒过来是因为，题目要求第一个比第二个数小，也提高一下效率
        {
            if(factor[i] == j && factor[j] == i)//一定不要忘记亲密数的定义
                printf("(%d,%d)",i,j);
        }
    }
    return 0;
}