02 质数问题

​ 质数又称素数，指的是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。值得注意的是，每一个数都可以分解成质数的乘积。

204 计数质数 (opens new window)

给定一个数字 n，求小于 n 的质数的个数。

输入一个整数，输出也是一个整数，表示小于输入数的质数的个数。

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

解析：

​ 埃拉托斯特尼筛法（Sieve of Eratosthenes，简称埃氏筛法）是非常常用的，判断一个整数是否是质数的方法。并且它可以在判断一个整数 n 时，同时判断所小于 n 的整数，因此非常适合这道题。其原理也十分易懂：从 1 到 n 遍历，假设当前遍历到 m，则把所有小于 n 的、且是 m 的倍数的整数标为和数；遍历完成后，没有被标为和数的数字即为质数。

​ 一般情况下标记和数时从 2m 开始标记，此处可以进一步优化，对于一个质数 m，如果从 2m 开始标记其实是冗余的，应该直接从 m^2 开始标记，因为 2m, 3m, … 这些数一定在 m^2 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等。

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> prime(n,true);
        int ans = 0;
        for(int i=2;i<n;++i){
            if(prime[i]){
                ++ans;
                if((long long)i*i < n){ // i^2 可能越界 用长整型表示
                    for(int j=i*i;j<n;j+=i){
                        prime[j] = false;
                    }
                }
            }
        }
        return ans;
    }
};

172 阶乘后的零 (opens new window)

给定一个非负整数，判断它的阶乘结果的结尾有几个 0。

输入一个非负整数，输出一个非负整数，表示输入的阶乘结果的结尾有几个 0。

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

解析：

​ 唯一分解定理：任何一个大于1的自然数 N，如果 N 不为质数，那么 N 可以唯一分解成有限个质数的乘积。例如：42 = 2×3×7, 75 = 3×5×5。

​ 每个尾部的 0 由 2 × 5 = 10 而来，因此可以把阶乘的每一个元素拆成质数相乘，统计有多少个 2 和 5 数对。明显的，质因子 2 的数量远多于质因子 5 的数量，因为每 4 个数字算作额外的因子 2，但是只有每 25 个数字算作额外的因子 5，因此可以进一步优化只统计阶乘结果里有多少个质因子 5。

​ 对于一个数的阶乘，就如之前分析的，5 的因子一定是每隔 5 个数出现一次，也就是下边的样子。n! = 1 * 2 * 3 * 4 * (1 * 5) * ... * (2 * 5) * ... * (3 * 5) *... * n。因为每隔 5 个数出现一个 5，所以计算出现了多少个 5，我们只需要用 n/5 就可以算出来。

但还没有结束，继续分析。... * (1 * 5) * ... * (1 * 5 * 5) * ... * (2 * 5 * 5) * ... * (3 * 5 * 5) * ... * n。每隔 25 个数字，出现的是两个 5，所以除了每隔 5 个数算作一个 5，每隔 25 个数，还需要多算一个 5。也就是我们需要再加上 n / 25 个 5。

​ 同理还会有每隔 5 * 5 * 5 = 125 个数字，会出现 3 个 5，所以还需要再加上 n / 125 。

​ 综上，规律就是每隔 5 个数，出现一个 5，每隔 25 个数，出现 2 个 5，每隔 125 个数，出现 3 个 5... 以此类推。最终 5 的个数就是 n / 5 + n / 25 + n / 125 ...

class Solution {
public:
    int trailingZeroes(int n) {
        if(n==0){
            return 0;
        }
        int a = n / 5;
        return a + trailingZeroes(a);
    }
};