9999阶乘

9999阶乘 using System; using System.Collections.Generic; using System.Linq; using Oyster.Math; namespace csdnTest { class Program { static void Main(string[] args) { DateTime beginTime = DateTime.Now; IntX result = Factorial(1000000); DateTime endTime = DateTime.Now; Console.WriteLine(endTime - beginTime); Console.WriteLine(result); Console.ReadKey(); } static IntX Factorial(int n) { int[] counter = GetPowCounter(n); SortedDictionary sDict = new SortedDict ionary(); //计算幂乘并将结果压入优先队列(使用优化过的大数乘 法,在计算相等规模的大数乘法时，效率最高) for (int i = 2; i <= n; i++) { if (counter[i] > 0) sDict.Add(IntX.Pow(i, (uint)counter[i]), fa lse); } IntX valueA = 1, valueB; //用SortedDictionary模拟优先队列进行最后的计算 while (sDict.Count > 1) { valueA = sDict.ElementAt(0).Key; valueB = sDict.ElementAt(1).Key; sDict.Remove(valueA); sDict.Remove(valueB); sDict.Add(valueA * valueB, false); } return sDict.ElementAt(0).Key; } //做质因数分解,以便使用幂乘进行计算 static int[] GetPowCounter(int n) { int[] pList = GetPrime(n); int[] pCounter = new int[n + 1]; for (int i = 0; i < pList.Length; i++) { int k = n; while ((k /= pList[i]) > 0) pCounter[pList[i]] += k; } return pCounter; } //生成质数列表 static int[] GetPrime(int n) { List prime = new List(); bool[] flags = new bool[n + 1]; for (int i = 2; i <= n; i++) { if (!flags[i]) prime.Add(i); for (int j = 0; j < prime.Count; j++) { if (prime[j] * i > n) break; flags[prime[j] * i] = true; if (i % prime[j] == 0) break; } } return prime.ToArray(); } } }