一直想写这篇关于算法的文章，但是由于看到园子里众多研究算法的高手让我一直没有决心写下来，但高手归高手，不是高手也可以写出来让高手们拍砖，所以今天就在这里献丑了。相亲数和完全数作为数学问题的确是顶级难题，可是拿来做娱乐就不同了，从刚接触编程时C语言书上的课后习题到两年前的Intel多核编程大赛，这个题目一直伴随着我们，让我们来娱乐一下吧。
简单说一下概念，相亲数是指两个正整数中，彼此的全部约数之和（本身除外）与另一方相等。举例来说：
220的全部约数(除掉本身)相加是：1+2+4+5+10+11+20+22+44+55+110=284
284的全部约数(除掉本身)相加的和是：1+2+4+71+142=220
所以220和284就是一对相亲数。
那什么是完全数呢？即它所有的真因子（即除了自身以外的约数）的和恰好等于它本身。例如：
第一个完全数是6，它有约数1、2、3、6，除去它本身6外，其余3个数相加，1+2+3=6
第二个完全数是28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28
概念不多说了，直接上算法。
算法一：直接计算约数之和
这是最直接的方式了，循环计算所有可能成为约数的数字然后加和，直接到不用做过多的解释，只要会写程序，用任何语言都能实现！
1: /// <summary>
2: /// 直接计算约数之和(串行)
3: /// </summary>
4: public class Algorithm1
5: {
6: private int GetSum(int num)
7: {
8: int sum = 1;
9: int limit = (int)Math.Sqrt(num);
10: for (int i = 2; i <= limit; i++)
11: if (num % i == 0) sum += i + num / i;
12: return sum;
13: }
14:
15: public void Run(int from, int to)
16: {
17: int perfertCount = 0;
18: int amicablePairCount = 0;
19: for (int num = from; num <= to; num++)
20: {
21: int sum1 = this.GetSum(num);
22: if (sum1 == num)
23: {
24: Console.WriteLine("{0}是完全数", num);
25: perfertCount++;
26: }
27: if (sum1 > num)
28: {
29: int sum2 = this.GetSum(sum1);
30: if (sum2 == num)
31: {
32: Console.WriteLine("{0}和{1}是一对相亲数", sum1, sum2);
33: amicablePairCount++;
34: }
35: }
36: }
37: Console.WriteLine("在{0}到{1}中共有{2}个完全数和{3}对相亲数", from, to, perfertCount, amicablePairCount);
38: }
39: } 测试代码，从2计算到5000000：
1: static void Main(string[] args)
2: {
3: var stopwatch = Stopwatch.StartNew();
4: Algorithm1 algorithm = new Algorithm1();
5: algorithm.Run(2, 5000000);
6: stopwatch.Stop();
7: Console.WriteLine("计算完成共花费{0}秒", stopwatch.Elapsed.TotalSeconds);
8: Console.ReadKey();
9: } 在我的ThinkPad R400上测试运行时间大概在51秒左右，速度能不能再提高呢，让我们看看.Net4.0为我们带来的并行计算的新特性表现如何。
1: /// <summary>
2: /// 直接计算约数之和(并行)
3: /// </summary>
4: public class Algorithm2
5: {
6: private int GetSum(int num)
7: {
8: int sum = 1;
9: int limit = (int)Math.Sqrt(num);
10: for (int i = 2; i <= limit; i++)
11: if (num % i == 0) sum += i + num / i;
12: return sum;
13: }
14:
15: public void Run(int from, int to)
16: {
17: int perfertCount = 0;
18: int amicablePairCount = 0;
19: Parallel.For(from, to, num =>
20: {
21: int sum1 = this.GetSum(num);
22: if (sum1 == num)
23: {
24: Console.WriteLine("{0}是完全数", num);
25: perfertCount++;
26: }
27: if (sum1 > num)
28: {
29: int sum2 = this.GetSum(sum1);
30: if (sum2 == num)
31: {
32: Console.WriteLine("{0}和{1}是一对相亲数", sum1, sum2);
33: amicablePairCount++;
34: }
35: }
36: });
37: Console.WriteLine("在{0}到{1}中共有{2}个完全数和{3}对相亲数", from, to, perfertCount, amicablePairCount);
38: }
39: } 注意第19行，我们使用System.Threading.Tasks下的Parallel类取代传统的for循环，由于在该算法中每一次计算都是独立的，所以很适合并行，废话不多说，直接运行看结果，运行时间在26秒左右，由于我的机器是双核，所以同样是从2计算到5000000，并行的时间差不多是之前的(51秒)一半，看来Parallel真是不错的新工具啊！当然，这个是从技术上达到了速度的提升，算法本质还没有变，那能不能从算法本身提高计算效率呢？答案当然是肯定的！
本文导航
- 第1页: 首页
- 第2页: 通过计算所有质因数来计算约数之和
- 第3页: 我还没想到哪里可以用空间来换取速度
