求N的阶乘中末尾有几个0

‘’’
给定一个整数N，数值b=N*(N-1)(N-2)…21
N的取值范围1~2**63-1
求数值b最后有多少个0
比如:N=5,输出1。数值b为120,数值b最后有1个0
比如N=2152887270861，输出？
‘’’

直接求N的阶乘（数据太大时会内存溢出）

def calTime(n):
    if n < 1:
        return '不在范围内'
    if n > (2** 63 - 1):
        return '不在范围内'
    b = 1
    b = math.factorial(n)
    print('数值b',b)
    s = str(b)
    r = s[::-1]
    #print(r)
    count = 0
    for i in r:
        if (i=='0'):
            count += 1
        else:
            break
    return count

执行以上的程序，如果N=2152887270861

Traceback (most recent call last):
  File "T6.py", line 55, in <module>
    print('数值b中0的个数为:',calTime(n))
  File "T6.py", line 16, in calTime
    b = math.factorial(n)
OverflowError: factorial() argument should not exceed 2147483647

不用递归，用循环，数据太大时程序执行太慢

def demo(num):
    factorial = 1
    if n < 1:
        return '不在范围内'
    if n > (2** 63 - 1):
        return '不在范围内'
    else:
       for i in range(1,num + 1):
           factorial = factorial*i
       print("%d 的阶乘为 %d" %(num,factorial))
       

正确思路

• 将n阶乘做质因数分解，将n阶乘表示成
  

其中a, m, n都是非负整数，且a不能被2和5整除。

• 上面的表达式中，每一对2和5都贡献了一个末尾的零，因此我们只要知道n的阶乘中有多少个因子2，有多少个因子5，求两者的最小值，即求m、k二者的最小值

• k,m的值
  n！= N (N-1) (N-2)…x 2 x 1

  
  综上，k<m

  • 求出k的值即为结果

def get_zero_num(n):
    num = 0
    while True:
        n = int(n / 5)
        if n == 0:
            break
        num = num + n

    return num

if __name__ == '__main__':
    n = 2152887270861
    print('数值b中0的个数为:',get_zero_num(n))