一个很有趣的编程题

碰巧和一个朋友聊到一个趣题

如何最好最快的方法求阶乘，也就是从1一直乘到n,

怎么样试试吧。




==================================================================================
一个很偶然的机会，谈到一个很有趣的编程题，阶乘的算法，阶乘是从1一直乘到n,刚听
到这个题，觉得很简单，用递归算法就可以搞定了，不过当来写这个代码的时候，才发觉
，原来自己想的过于简单，由于n是不确定的，所以这个数值可能非常的大，远远大于
我们的基本数据类型。那么怎样来表示这个数据结构了，一下就去思考这个方面的问题，
如果是这样想的，那你就是中圈套了，数据结构是根本就解决不了的，只有在算法上做文
章，那么应该是如何的算法了，其实就是最简单的9*9乘法口诀了，就可以搞定了。

觉得很过瘾，特记下来，算法是个很有趣的研究。一个清晰和简洁的算法大有耳目一新的感
觉。
==================================================================================

lz很强悍啊，
-------------------
文章: 0
积分: 70
来自: 深圳

我的想法：
（1）最快的方法就是打一个表，然后去查询。就是有点不实际。
（2）1＊2＊3＊....*n = X,那么X＝(p1^q1)*(p2^q2)*....*(pk^qk)

k是小于X的质数的个数，pi是第i个质数，

qi是该质数的指数，可以用logpi(N)方法求得

pi^qi可以使用快速幂，复杂度是log2(qi)

回比直接算要快

qi是该质数的指数，可以用logpi(N)方法求得


这个是不对的

确实，最后是加法和乘法。

这个是有确定算法的

int q=0;
while(n>0){
   q+=n/p;
   n=n/p;
}

这个可以~~

如果不要求精确值，阶乘用Stirling最简单~~

具体的程序编码的伪代码是怎样的了

阶乘计算是有公式的（近似）

即使这个公式的运算量也是非常的客观。

运算量跟阶乘比 几乎可以忽略~~