LeetCode50天刷题计划第二季（Day 32 — 阶乘后的零（13.20-14.00）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

今天是数学题

一、题目

阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1

示例

示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：
输入：n = 0
输出：0

提示

0 <= n <= 104

进阶

你可以设计并实现对数时间复杂度的算法来解决此问题吗？

二、思路

首先，阶乘后有多少个0取决于因数中有多少个10，而10=2*5，因此只需要找到因数2的个数和因数5的个数，然后取其中的较小值即可
那么如何获取1~n中因数p（p为素数）的个数呢？

三、代码

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count=0
        while(n>=5):
            n=n//5 #整除，向下取整
            count+=n #累计
        return count

1
2
3
4
5
6
7
8