编程之美127页,N!中含有质因数2的个数 = [N/2] + [N/4] + [N/8] + [N/16] + .....
要理解上式,先看
编程之美126页,N!中含有质因数5的个数Z
举例:N = 25
,即1~25
5的倍数(5,10,15,20,25)贡献一个5
25的倍数贡献一个5
虽然25可以贡献两个5,但是已经在5的倍数中贡献一次了,所以这里就统计一次
也就是说,对于每一个5 M,N只统计一次5,虽然它本身有多个5的质因数,但是已经在前面M-1计算过,所以只需统计一次即可
ret = 0;
while(N) //每执行一次迭代,就求出了 有多少个 5^M 贡献5
{
ret += N / 5; //表示 1-N 中能奉献出5的数的个数
N /= 5;
}
同样思路,便可以理解开头的公式了。