相亲数amp;完全数最简单算法

article/2025/10/8 9:12:08

今天看到博客园一位仁兄的相亲数，整体感觉不错。

原文出处：http://www.cnblogs.com/devil0153/archive/2010/08/22/AmicablePair-And-PerfectNumber.html

但有些算法感觉有些大材小用，随手写了一个最简单的相亲数的判断程序：

运行效果不是想象中的差，没进行任何的优化：

其中只是避开了分解质因数，求解复杂运算

代码

1 #include < stdio.h >
2 #include < time.h >
3 /* ----------------
4 计算相亲数的快速算法
5 最直接的代码用时：3088ms
6 平台：T2330 1.6GHZ
7 ----------------- */
8 #define MAX_TEST 5000000
9 long nTable[MAX_TEST]; // 素数表
10 char nFlag[MAX_TEST];
11 // 构造未标记用于降低内存使用
12
13 void printConsole()
14 {
15      for ( long i = 2 ;i < MAX_TEST;i ++ )
16     {
17          if (nFlag[i] == 0 )
18         {
19              if (nTable[i] < MAX_TEST && (nTable[nTable[i] + 1 ] + 1 == i))
20                 printf( " %ld\t%ld\n " ,i,nTable[i] + 1 );
21             nFlag[nTable[i] + 1 ] = 1 ;
22         }
23     }
24 }
25
26 int main()
27 {
28      long j = 0 ;
29      double startTime,endTime;
30     startTime = ( double )clock();
31      for ( long i = 2 ;i < MAX_TEST;i ++ )
32     {
33         j = (i << 1 );
34          while (j < MAX_TEST)
35         {
36             nTable[j] += i;
37             j += i;
38         }
39     }
40     endTime = ( double )clock();
41     printf( " Total Run Time:%f\n " ,endTime - startTime);
42      // printf("数值：%ld\n",nTable[220]);
43     printConsole();
44      return 1 ;
45 }