有趣的编程计算相亲约会数(上)

我一直想写这篇关于算法的文章，但我没有信心记录下来，因为我在花园里看到了许多科学研究算法的伟大之神，但伟大的上帝属于专家。不是伟大的上帝能表达出来，让伟大的上帝拍砖头，所以我今天在这里献丑。相亲和约会的数量和完整数量确实是数学问题的顶级难点，但作为游戏娱乐是不同的，从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：立即计算约数总和

这也是最直接的方式。循环系统计算机可能成为大约数字，然后加和。它不需要直接做太多的表达。只要它能写程序，就可以用任何语言表达！

1: ///

2: /// 立即计算约数总和(串行通信)
3: ///

4: public class Algorithmm1
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: Algorithmm1 algorithm = new Algorithmm1();
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: ///

2: /// 立即计算约数总和(并行处理)
3: ///

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核，所以用2计算到5万，组合时间约为以前（51秒）的一半，看起来派对真的是一个很好的工具！自然，这是为了提高技术速度，优化算法的本质没有改变，那么优化算法本身就不能提高计算效率呢？自然，这是为了提高技术速度，优化算法的本质没有改变，那么优化算法本身就不能提高计算效率呢？答案当然是肯定的！