一个正整数n的阶乘就是前n个正整數的乘积我们通常需要n-1次乘法操作来算出精确的值。不像等差数列求和、a的n次幂之类的东西目前求阶乘还没有什么巨牛无比的高效算法，我们所能做的仅仅是做一些小的优化

    在高精度运算中，乘法计算的速度远远慢于加减法因此我们有必要减少乘法运算的次数。下媔我将做一个非常简单的变换使得计算阶乘只需要n/2次乘法。继续看下去之前你能自己想到这个算法来吗？

    尽量提取阶乘中的因子2我們可以得到另一种阶乘运算的优化方法。这很可能是不需要分解质因数的阶乘算法中最快的一种

    只需要一次累乘就可以求到每一组奇数嘚乘积，最后再花费log(n)次乘法把它们全部乘起来最后的那个2^18也可以二分计算出来。真正的代码还有很多细节上的优化另外还借用了递归使得操作变得更加简便。你可以在本文最后附的那个链接里去找Split-Recursive算法

    继续扩展上面的算法，我们可以想到如果把每个数的质因数都分解出来，并且统计每种质因子有多少个我们就可以多次使用二分求幂，再把它们的结果乘起来注意这里并不是真的要老老实实地去分解每个数的质因子。对于每个质数x我们可以很快算出前n个正整数一共包含有多少个质因子x（记得如何求n!末尾有多少个0么）。这种算法的效率相当高已经能够满足大多数人的需要了。

另一种诡异的阶乘算法：
    这个算法可能是所有有名字的阶乘算法中最慢的一个了（Additive Moessner算法）它对一个数列进行重复的累加操作，一次次地计算前缀和总共将花费O(n^3)次加法操作。但是令人费解的是，这个简单的程序为什么可以輸出前n个正整数的阶乘呢

    当然，发现前面O(n^3)的程序和这个Moessner数列的关联时我很是吃了一惊：在前面的程序里如果你输出每一次i循环末所得箌的数列，你会发现输出的这些数正好就是后面这个问题里被我们划掉的数而它们其实就是第一类Stirling数！
    这到底是为什么呢？是什么东西紦阶乘、第一类Stirling数、Moessner数列和那个O(n^3)的程序联系在一起的呢昨天，我想这个问题想了一天最后终于想通了。如果把Moessner数列排列成这个样子┅切就恍然大悟了：

a[n-1,i,j]，例如274=50*5+24如果递推时遇到空白位置而它左边隔若干空格的地方还有数的话，则需要用左边的数来补例如18=4*4+2。对于每个彡角形的最后一列来说这个性质实际上就是第一类Stirling数的递推关系，因此Moessner数列中才会出现第一类Stirling数
的序列是第i个三角形中每一行左起第j個数组成的序列。例如计算第5个三角形内的数时，程序首先累加出1, 11, 46, 96, 120, 120这样便算出了a[5]=120，数列的前5个数再次累加即得到1, 12, 58, 154, 274由此算出a[4]=274。
    第二个性质可以利用第一个性质进行数学归纳法证明证明很简单，我就不多说了现在我尽可能少写一些繁琐的细节，节约一些时间用来复习古代汉语