趣味编程之计算相亲数(上)

.Net编程自动调试监视工具(Auto Debug For .Net)v1.5 注册专业版

• 类型：编程辅助大小：1.8M语言：英文 评分：6.0
• 标签：

立即下载

先说一下原理：记得小学的奥赛有一个题型是计算一个自然数的约数的个数(现在还有没有不清楚)，截法很简单，先分解质因数，然后把所有质因子的幂加一再相乘就是约数的个数，例如数字36=2^2×3^2，那么36就有(2+1)×(2+1)=9个约数(1,2,3,4,6,9,12,18,36)。其实能算出有9个约数，自然可以计算9个约数是什么，是2个2和2个3排列组合的结果，剩下的就不用我废话了，该算法的思路就是先分解质因数然后在逐个计算约数并加和，上代码：

1: /// <summary>
2: /// 通过计算所有质因数来计算约数之和（串行）
3: /// </summary>
4: public class Algorithm3
5: {
6: private int GetNextFactor(int num)
7: {
8: int limit = (int)(Math.Sqrt(num));
9: for (int i = 2; i <= limit; i++)
10: if (num % i == 0)
11: return i;
12: return num;
13: }
14: private List<int> Decomposition(int num)
15: {
16: var factors = new List<int>();
17: while (true)
18: {
19: var divisor = GetNextFactor(num);
20: factors.Add(divisor);
21: if (divisor == num) break;
22: num = num / divisor;
23: }
24: return factors;
25: }
26: private int Sum(List<int> divisors)
27: {
28: int sum = 0;
29: for (int i = 0, count = divisors.Count - 1; i < count; i++)
30: sum += divisors[i];
31: return sum;
32: }
33: private int GetSum(List<int> factors)
34: {
35: if (factors.Count == 1) return 1;//质数
36: var divisors = new List<int>() { 1 };
37: var factorPows = new List<List<int>>() { new List<int>() { factors[0] } };
38: for (int i = 1, count = factors.Count; i < count; i++)
39: {
40: var length = factorPows.Count;
41: if (factors[i] == factorPows[length - 1][0])
42: factorPows[length - 1].Add(Convert.ToInt32(Math.Pow(Convert.ToDouble(factors[i]), Convert.ToDouble(factorPows[length - 1].Count + 1))));
43: else
44: factorPows.Add(new List<int>() { factors[i] });
45: }
46: for (int f = 0, fCount = factorPows.Count; f < fCount; f++)
47: for (int d = 0, dCount = divisors.Count; d < dCount; d++)
48: for (int p = 0, pCount = factorPows[f].Count; p < pCount; p++)
49: divisors.Add(divisors[d] * factorPows[f][p]);
50: return Sum(divisors);
51: }
52: public void Run(int from, int to)
53: {
54: int perfertCount = 0;
55: int amicablePairCount = 0;
56: for (var num = from; num < to; num++)
57: {
58: int sum1 = this.GetSum(Decomposition(num));
59: if (sum1 == num)
60: {
61: Console.WriteLine("{0}是完全数", num);
62: perfertCount++;
63: }
64: if (sum1 > num)
65: {
66: int sum2 = this.GetSum(Decomposition(sum1));
67: if (sum2 == num)
68: {
69: Console.WriteLine("{0}和{1}是一对相亲数", sum1, sum2);
70: amicablePairCount++;
71: }
72: }
73: }
74: Console.WriteLine("在{0}到{1}中共有{2}个完全数和{3}对相亲数", from, to, perfertCount, amicablePairCount);
75: }
76: } 先看速度如何，是否比算法一更快，从2计算到5000000花费近27秒，几乎与算法一的并行版本接近，果然快很多，那么快在哪里了呢？算法一做了大量的取模和除法操作，相比于加、减、乘等操作这些操作都是很耗时的，而算法二先计算质因数，减少了很多取模和除法操作，取而代之的是很多乘法和指数运算，性能自然得到提升，但还算细心的我并没有就此下结论，我把计算范围缩小到2到100000，此时，算法一花费时间是0.18秒而算法而则是0.36秒，算法一反而取胜了，其实道理很简单，随着数字的增大，算法一计算取模和除法的操作增加也不断增加，而算法二随着数字增大计算次数却增加不明显，因为分解质因数其实是找质数的过程，但找到第一个质因数后，数字就变小了，计算量并没增加多少，相反，找到的质因数越多，计算约数的计算量就越大，所以在数字不大(相对不大)的领域里，试商次数不多所以算法一很快完成了计算，而算法二相对于算法一的却没什么太大优势，但随着数字的变大，算法二的优势会越来越明显！例如我从5000000计算到5500000，算法一就豪无优势了，落后算法二一半都不止，这让我想起了一个古老的但却众所周知的梵塔问题，算法一就是这样一个梵塔……

当然我也没忘记把这个算法改成并行版本，我就不贴代码了，只要改第56行的for就可以了，从2计算到5000000花费在16秒左右，这样我们已经从最初的51秒降低到16秒，还能更快吗？我绞尽脑汁暂时还没什么结果，因为我发现最后所花的时间都是在寻找质数上了，难怪数学界的顶级难题都跟质数有关或者围绕质数展开，还有我们程序员熟悉的加密算法RSA，也是基于大整数难以分解的“特性”上，如果不幸被我找到了快速分解算法我就不用在这写博客啦，扯远了，还是回归娱乐吧，我们还有没有办法让它再快点呢？

算法二SP1：之所以叫SP1是因为它并没有本质上的更改，只是在外围让它显得更快。话说算法界有两大秘籍，九阴真经和九阳神功——都不是，开个玩笑，其实没什么秘籍，而是方法论，无非就是时间换空间和空间换时间，根据我们的需要，时间和空间在我们的代码中转换来转换去，既然我追求的是速度，那自然是用空间来换时间喽。