题目分析

来一道简单题给小伙伴们放松放松。

数学

相信每个学习编程的同学们都遇到过这个题目或者类似这个题目，当时我遇到的是判断一个数是否为质数。什么是质数，质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。如7，只能分解成1和7的乘积，说明7是质数，8就不是质数，因为可以分解为2和4的乘积，9也不是质数，可以分解为3和3的乘积。

因此算法也非常明显，判断n是否为质数，从2遍历到$\sqrt{n}$，如果能整除，说明不是质数。如果都不能整除，说明是质数。

这个题目是判断小于n的质数数量，那么就逐一枚举n，如果是质数则res++即可。

算法的**时间复杂度为$O(n\sqrt{n})$，空间复杂度为$O(1)$**。

#include<iostream>

using namespace std;

class Solution {
public:
    int countPrimes(int n) {
        int res = n >= 3 ? 1 : 0;
        for (int i = 3; i < n; i++) {
            int sq = sqrt(i) + 1;
            for (int j = 2; j <= sq; j++) {
                if (i % j == 0) break;
                if (j == sq) res++;
            }
        }
        return res;
    }
};

埃氏筛

该算法由希腊数学家厄拉多塞（EratosthenesEratosthenes）提出，称为厄拉多塞筛法，简称埃氏筛。

算法的思路非常简单，有三个要点。

如果一个数是质数，那么其倍数一定都是合数。如7是质数，那么14，21，28…都是合数。
如果一个数是合数，不需要判断其倍数，一定已经判断过了。如14是合数，因为14可以分解为2和7的乘积，那么在2中已经将14，28，42…判断过了，因此不用判断倍数了。
分析质数k时，直接从k x k开始判断倍数即可。如分析7时，直接判断49， 56， 63…，不需要判断14， 21， 28…，因为k x m(m < k)时，已经在分析m时判断过了。14在分析2的时候已经判断过了，21在分析3的时候已经判断过了。

代码也比较简单，记住上面三个要点也很容易可以写出来。

算法的**时间复杂度为$O(nlog(log(n)))$，空间复杂度为$O(n)$**，时间复杂度的推导非常繁琐，有兴趣的小伙伴可以找度娘。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> nums(n, true);
        int res = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i]) {
                res++;
                if (long long(i) * i < n) {
                    for (int j = i * i;j < n; j += i) { nums[j] = false; }
                }
            }
        }
        return res;
    }
};

线性筛

这个方法就更绕人了，小伙伴们能写出埃氏筛即可，线性筛作为了解。

在埃氏筛中，对于45这个数，在分析3的时候进行了赋值，在分析5的时候也进行了赋值。这会浪费一部分时间复杂度，可以从中进一步优化。

我们想对一个数只标记一次，用最小因子和最大因子标记即可，如45，就用3和15进行标记，不需要用5和9再次标记。

如果一个数x可以被一个质数n整除，设x = k x n，那么对于合数y = x * m，其中m为另一个更大的质数，就不需要标记了，一定会被$\frac{x}{n} \cdot m$标记。例如15可以被3整除，那么对于75 = 15 * 5来说，75一定会被$\frac{15}{3} \cdot 5 = 25$标记。

$$y = x \cdot m = k \cdot n \cdot m = k \cdot m \cdot n$$

其中n是最小的质数因子。

因此我们在分析15的时候，只用将30， 45， 60…标记即可，对于75这个数，以后有25会对其标记。

可以再优化的是：我们只用标记质数，在分析15的时候，其实只用标记30和45，因为15 x 2 = 30， 15 * 3 = 45，2和3都是质数。因为合数一定可以分解为最小的质数因子，所以，60可以分解为4 x 15，4是质数，可以分解为2 x 2，因此可以写成30 x 2，会被30标记，也不用在这里标记。

综上所述，合数不用标记，只用标记到能整除的第一个质数即可。这样每个数只用标记一次。算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int countPrimes(int n) {
        vector<int> prime;
        vector<bool> nums(n, true);
        for (int i = 2; i < n; i++) {
            if (nums[i]) { prime.push_back(i); }
            for (int j = 0; j < prime.size() && i * prime[j] < n; j++) {
                nums[i * prime[j]] = false;
                if (i % prime[j] == 0) { break; }
            }
        }
        return prime.size();
    }
};

刷题总结

还是埃氏筛简单易懂，而且时间复杂度很低，在1e10的数量中，log(log(1e10)) = 5，也相当于几乎线性的时间复杂度。