趣味編程之計(jì)算相親數(shù)(上)

第 2 頁(yè) 通過(guò)計(jì)算所有質(zhì)因數(shù)來(lái)計(jì)算約數(shù)之和
算法二：通過(guò)計(jì)算所有質(zhì)因數(shù)來(lái)計(jì)算約數(shù)之和

先說(shuō)一下原理：記得小學(xué)的奧賽有一個(gè)題型是計(jì)算一個(gè)自然數(shù)的約數(shù)的個(gè)數(shù)(現(xiàn)在還有沒(méi)有不清楚)，截法很簡(jiǎn)單，先分解質(zhì)因數(shù)，然后把所有質(zhì)因子的冪加一再相乘就是約數(shù)的個(gè)數(shù)，例如數(shù)字36=2^2×3^2，那么36就有(2+1)×(2+1)=9個(gè)約數(shù)(1,2,3,4,6,9,12,18,36)。其實(shí)能算出有9個(gè)約數(shù)，自然可以計(jì)算9個(gè)約數(shù)是什么，是2個(gè)2和2個(gè)3排列組合的結(jié)果，剩下的就不用我廢話了，該算法的思路就是先分解質(zhì)因數(shù)然后在逐個(gè)計(jì)算約數(shù)并加和，上代碼：

1: /// <summary>
2: /// 通過(guò)計(jì)算所有質(zhì)因數(shù)來(lái)計(jì)算約數(shù)之和（串行）
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;//質(zhì)數(shù)
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}是完全數(shù)", 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}是一對(duì)相親數(shù)", sum1, sum2);
70: amicablePairCount++;
71: }
72: }
73: }
74: Console.WriteLine("在{0}到{1}中共有{2}個(gè)完全數(shù)和{3}對(duì)相親數(shù)", from, to, perfertCount, amicablePairCount);
75: }
76: } 先看速度如何，是否比算法一更快，從2計(jì)算到5000000花費(fèi)近27秒，幾乎與算法一的并行版本接近，果然快很多，那么快在哪里了呢？算法一做了大量的取模和除法操作，相比于加、減、乘等操作這些操作都是很耗時(shí)的，而算法二先計(jì)算質(zhì)因數(shù)，減少了很多取模和除法操作，取而代之的是很多乘法和指數(shù)運(yùn)算，性能自然得到提升，但還算細(xì)心的我并沒(méi)有就此下結(jié)論，我把計(jì)算范圍縮小到2到100000，此時(shí)，算法一花費(fèi)時(shí)間是0.18秒而算法而則是0.36秒，算法一反而取勝了，其實(shí)道理很簡(jiǎn)單，隨著數(shù)字的增大，算法一計(jì)算取模和除法的操作增加也不斷增加，而算法二隨著數(shù)字增大計(jì)算次數(shù)卻增加不明顯，因?yàn)榉纸赓|(zhì)因數(shù)其實(shí)是找質(zhì)數(shù)的過(guò)程，但找到第一個(gè)質(zhì)因數(shù)后，數(shù)字就變小了，計(jì)算量并沒(méi)增加多少，相反，找到的質(zhì)因數(shù)越多，計(jì)算約數(shù)的計(jì)算量就越大，所以在數(shù)字不大(相對(duì)不大)的領(lǐng)域里，試商次數(shù)不多所以算法一很快完成了計(jì)算，而算法二相對(duì)于算法一的卻沒(méi)什么太大優(yōu)勢(shì)，但隨著數(shù)字的變大，算法二的優(yōu)勢(shì)會(huì)越來(lái)越明顯！例如我從5000000計(jì)算到5500000，算法一就豪無(wú)優(yōu)勢(shì)了，落后算法二一半都不止，這讓我想起了一個(gè)古老的但卻眾所周知的梵塔問(wèn)題，算法一就是這樣一個(gè)梵塔……

當(dāng)然我也沒(méi)忘記把這個(gè)算法改成并行版本，我就不貼代碼了，只要改第56行的for就可以了，從2計(jì)算到5000000花費(fèi)在16秒左右，這樣我們已經(jīng)從最初的51秒降低到16秒，還能更快嗎？我絞盡腦汁暫時(shí)還沒(méi)什么結(jié)果，因?yàn)槲野l(fā)現(xiàn)最后所花的時(shí)間都是在尋找質(zhì)數(shù)上了，難怪?jǐn)?shù)學(xué)界的頂級(jí)難題都跟質(zhì)數(shù)有關(guān)或者圍繞質(zhì)數(shù)展開(kāi)，還有我們程序員熟悉的加密算法RSA，也是基于大整數(shù)難以分解的“特性”上，如果不幸被我找到了快速分解算法我就不用在這寫(xiě)博客啦，扯遠(yuǎn)了，還是回歸娛樂(lè)吧，我們還有沒(méi)有辦法讓它再快點(diǎn)呢？

算法二SP1：之所以叫SP1是因?yàn)樗�并沒(méi)有本質(zhì)上的更改，只是在外圍讓它顯得更快。話說(shuō)算法界有兩大秘籍，九陰真經(jīng)和九陽(yáng)神功——都不是，開(kāi)個(gè)玩笑，其實(shí)沒(méi)什么秘籍，而是方法論，無(wú)非就是時(shí)間換空間和空間換時(shí)間，根據(jù)我們的需要，時(shí)間和空間在我們的代碼中轉(zhuǎn)換來(lái)轉(zhuǎn)換去，既然我追求的是速度，那自然是用空間來(lái)?yè)Q時(shí)間嘍。