亲密数

    如果整数A的全部因子（包括1，不包括A本身）之和等于B，并且整数B的全部因子(包含1，不包含B本身)之和等于A，称整数A和B为亲密数。求解3000以内的全部亲密数。

    遇到这种题目，我们首先想到的是，我们需要先求出一个数的所有因子之和，然后通过循环去判断两个是否是亲密数。因此通过穷举法，我们即可求出所有的亲密数，代码如下：

#include <stdio.h>
#define N 3000

int factorSum(int n)
{
  int i,sum = 0;
  for(i=1; i<n; i++)
    if(n%i == 0)
      sum += i;

  return sum;
}

int isFriend(int num1, int num2, int sum1, int sum2)
{
  if(num1 == sum2 && num2 == sum1)
    return 1;
  else
    return 0;
}

void friendly()
{
  int i,j,x[N];
  for(i=0;i<N;i++)
    x[i] = factorSum(i+1);

  for(i=0; i<N; i++){
    if(x[i] != -1){
      for(j=i+1; j<N; j++)
        if(isFriend(x[i],x[j],i+1,j+1)){
          printf("(%d,%d) ",i+1,j+1);
          x[j] = -1;
        }
    }
  }
}

int main(int argc, char* argv[])
{
  printf("there are following friendly numbers from 1 to %d \n",N);
  friendly();
  printf("\n");
  return 0;
}

执行结果如下：

peng@ubuntu:~/src/test/c/suanfa/miaoqu$ ./a.out 

there are following friendly numbers from 1 to 3000

(220,284) (1184,1210) (2620,2924)