100的阶乘后面有几位0？

Question

5! = 120, 末尾有一个0.
6! = 720, 末尾有一个0.
10! =3628800, 末尾有两个0.

//阶乘函数
function factorial(n) {
 let result = 1;  
 while( n > 1) {
   result = result * n;
   n--;
 }
 return result;
}
var result = factorial(100);
console.log(result); //9.332621544394418e+157

//计算阶乘结果后面有几个0
var index = 0;
if(result % 10 == 0) {
    while(result % 10 == 0) {
          result = result / 10;
        index++;
    }
} else {
   console.log('No zero in the end!');
}
console.log(index);

这个代码哪里不对？ 100的阶乘末尾的零是有24位的。这个程序算不出来正确结果。如果是因为数字太大计算不出来的话，原理是什么？

Answer 1

超过整型上限的不能存成整数，会存成浮点数

可以计算每个数里面有几个5的因子数，加起来看是多少，因为2的因子书肯定比5多

var num = 0;
for(let i = 1; i <= 100; i++) {
    let count = 0;
    let j = i;
    while ( j > 0 && j % 5 == 0 ) {
        j = j / 5;
        count ++;
    }
    num += count;
}
console.log(num);

如果一定要计算阶乘的话，请自己写大数乘法，比方说用字符串存储数字

Answer 2

程序并没有问题。只是超出了JavaScript Number类型的储存上限，所以出现了错误。

JavaScript没有内置的Big Number, Big Decimal一类。如果实现需要，只能自己封装。

不过这个问题可以用数学的方法简单分析。

10 = 2 * 5（质因数分解）

从最末尾开始连续地每出现一个0，即表示有一个 (2 * 5) 组出现。
而对于正整数 N，在[0, N]范围内，质因子中含有 2 的总是会比质因子含有 5 的要多。即如果质因子有 5 的数字总数为 a，那么质因子为2的总数 b >= a。因此，有x个质因子含有 5 的数，就有至少x个含有 2 的数。

于是，只要需要知道质因数含有 5 的数字有多少个，即可知道末尾连续出现 0 的个数有多少。

javascript：

function calc(n) {
    let count = 0
    // 因为可能出现一个数的质因子有多个5
    while (n >= 5) {
        n =  Math.floor(n/5)
        count += n
    }
    return count
}

比如：
calc(4) = 0
calc(5) = 1
calc(6) = 1
calc(10) = 2

calc(100) = 24

所以是末尾是 24 个连续的0。

Answer 3

function getZeros(n) {
  let ans = 0;
  while (n) {
    ans += ~~(n / 5);
    n = ~~(n / 5);
  }
  return ans;
}

没验证

Answer 4

这么玩儿，不怕数字大。。。

function findZeros (num) {
    var base = 5,
        result = 0;

    while (num >= base) {
        result += Math.floor(num / base);
        base *= 5;
    }

    return result;
}

Answer 5

count(0)=min(int(100/2)+int(100/4)+int(100/8)+int(100/16)+int(100/32)+int(100/64),int(100/5)+int(100/25))

Answer 6

10因质分解后: 10=2*5
凡是数结尾为0的,都是由2和5配对相乘得到的.
可以对1,2,3,4,...,100进行因质分解,统计得到的2和5的数量.那么100!的结尾的0数量就是2和5数量最少的一个.

# coding: utf-8


def factor(num):
    primes = []
    for i in xrange(2, num/2+1):
        
        while num % i == 0:
            num = num / i
            primes.append(i)
    return primes


def main():
    factors = [] # 2是质数

    for i in xrange(1, 101):
        primes = factor(i)
        if not primes:
            primes.append(i)
        factors.extend(primes)

    print "--------------"
    print "2的数量:", factors.count(2)
    print "5的数量:", factors.count(5)


def verify():
    product = 1
    for i in xrange(1, 101):
        product = product*i

    count = 0
    for i in str(product)[::-1]:
        if i == '0':
            count += 1
        else:
            break
    print "验证结果:", count

if __name__ == '__main__':
    main()
    verify()

---

2的数量: 97

5的数量: 24

验证结果: 24

[Finished in 0.0s]