设n=a0+a1p+a2p^2+…+a(k)*p^k
对任意正整数n,n!含有的素数因子p的个数为[n/p]+[n/p^2]+[n/p^3]+...
[a]代表a的整数部分
因为0<=ai
所以[n/p]+[n/p^2]+[n/p^3]+...
=(a1+a2p+a3p^2+a4p^3...+a(k)p^(k-1))+(a2+a3*p+a4p^2+...+a(k)p^(k-2))+...+(a(k-1)+a(k)p)+a(k)
=a1+a2(1+p)+a3(1+p+p^2)+a4(1+p+p^2+p^4)+...+a(k)*(1+p+p^2+...+p^(k-1))
=(p-1)(a1(p-1)+a2(p^2-1)+a3*(p^3-1)+a4*(p^4-1)+...+a(k)*(p^k-1))
=(p-1)(a0+a1p+a2p^2+...+a(k)p^k-(a0+a1+a2+...+ak))
=(n-Sn)/(p-1)