解1： 流行的解法是，如果 N！= K10M，且K不能被10整除，则 N！末尾有 M 个0。考虑 N！可以进行质因数分解，N！= (2X) * (3Y) * (5Z)..., 则由于10 = 25，所以0的个数只与 X 和 Z 相关，每一对2和5相乘得到一个 10，所以 0 的个数 M = min(X， Z)，显然 2 出现的数目比 5 要多，所以 0 的个数就是 5 出现的个数。由此可以写出如下代码：
/** * N!末尾0的个数 */ int numOfZero(int n) { int cnt = 0, i, j; for (i = 1; i <= n; i++) { j = i; while (j % 5 == 0) { cnt++; j /= 5; } } return cnt; } 复制代码解2： 继续分析可以改进上面的代码，为求出1到N的因式分解中有多少个5，令 Z=N/5 + N/(52) + N/(53)+... 即 N/5 表示 1 到 N 的数中 5 的倍数贡献一个 5，N/(52) 表示 52 的倍数再贡献一个 5...。举个简单的例子，比如求1到100的数因式分解中有多少个5，可以知道5的倍数有20个，25的倍数有4个，所以一共有24个5。代码如下：
/** * N!末尾0的个数-优化版 */ int numOfZero2(int n) { int cnt = 0; while (n) { cnt += n/5; n /= 5; } return cnt; } 复制代码总结： 上面的分析乏善可陈，不过需要提到的一点就是其中涉及到的一条算术基本定理，也就是 任意大于1的自然数都可以分解为质数的乘积，而且该分解方式是唯一的。 定理证明分为两个部分，存在性和唯一性。证明如下：
存在性证明
使用反证法来证明，假设存在大于1的自然数不能写成质数的乘积，把最小的那个称为n。自然数可以根据其可除性（是否能表示成两个不是自身的自然数的乘积）分成3类：质数、合数和1。
首先，按照定义，n大于1。
其次，n 不是质数，因为质数p可以写成质数乘积：p=p，这与假设不相符合。因此n只能是合数，但每个合数都可以分解成两个严格小于自身而大于1的自然数的积。设 n = a*b，a 和 b都是大于1小于n的数，由假设可知，a和b都可以分解为质数的乘积，因此n也可以分解为质数的乘积，所以这与假设矛盾。由此证明所有大于1的自然数都能分解为质数的乘积。
唯一性证明
当n=1的时候，确实只有一种分解。
假设对于自然数 n>1，存在两种因式分解: n=p1...pm = q1...qk，p1<=...<=pm， q1<=...<=qk，其中 p 和 q 都是质数，我们要证明 p1=q1，p2=q2...如果不相等，我们可以设 p1 < q1，从而 p1 小于所有的 q。由于 p1 和 q1 是质数，所以它们的最大公约数为1，由欧几里德算法可知存在整数 a 和 b 使得 a * p1 + b * q1 = 1。因此 a * p1 * q2...qk + b * q1 * q2...qk = q2...qk (等式1)。由于 q1...qk = n，因此等式1左边是 p1 的整数倍，从而等式1右边的 q2...qk 也必须是 p1 的整数倍，因此必然有 p1 = qi，i > 1。而这与前面 p1 小于所有的 q 矛盾，因此，由对称性，对 p1 > q1 这种情况可以得到类似结论，故可以证明 p1 = q1，同理可得 p2 = q2...pm=qk，由此完成唯一性的证明。
3.1-N正整数中1的数目题： 给定一个十进制正整数N，求出从 1 到 N 的所有整数中包含 1 的个数。比如给定 N=23，则包含1的个数为13。其中个位出现1的数字有 1，11，21，共3个，十位出现1的数字有 10，11...19 共10个，所以总共包含 1 的个数为 3 + 10 = 13 个。
分析： 最自然的想法莫过于直接遍历1到N，求出每个数中包含的1的个数，然后将这些个数相加就是总的 1 的个数。需要遍历 N 个数，每次计算 1 的个数需要 O(log10N)，该算法复杂度为 O(Nlog10N)。当数字N很大的时候，该算法会耗费很长的时间，应该还有更好的方法。
解： 我们可以从1位数开始分析，慢慢找寻规律。
当 N 为 1 位数时，对于 N>=1，1 的个数 f(N) 为1。
当 N 为 2 位数时，则个位上1的个数不仅与个位数有关，还和十位数字有关。
当 N=23 时，个位上 1 的个数有 1、11、21 共3个，十位上1的个数为 10，11...19 共10个，所以 1 的个数 f(N) = 3+10 = 13。如果 N 的个位数 >=1，则个位出现1的次数为十位数的数字加1；如果 N 的个位数为0，则个位出现 1 的次数等于十位数的数字。