一、前言

质数的定义：质数，又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。

我们先来看容易想到的方法。

当我们需要统计 [2,n] 之间的质数时，很容易想到通过取 [2,n] 之间其中的每一个数x,再遍历 [2,x - 1] 中的每一个数 y，判断 y 是否为 x 的因数，若找到一个，就说明 x 不是质数。

又众所周知🤔如果 y 是 x 的因数，那么 \frac{y}{x} 也必然是 x 的因数（比如 2 是 6 的因数那么 3 也是 6 的因数，即 2 \times 3 = 3 \times 2）。也就是说我们不需要像上面那样遍历 [2,x - 1]，只需要遍历 [2,\sqrt{x}] 中的每一个数y就可以判断x是不是质数了😎👍。

这样做的时间复杂度是 O(n \sqrt{n})，但是枚举没有考虑到数与数的关联性，因此难以再继续优化时间复杂度。接下来介绍一种常见的算法，该算法由希腊数学家厄拉多塞（Eratosthenes）提出，称为厄拉多塞筛法，简称埃氏筛。

二、简介

我们可以这样想：如果x是质数，那么大于 x 的 x 的倍数 2x,3x,…一定不是质数，因此我们可以从这里入手。

我们设 isPrime[i] 表示数 i 是不是质数，如果是质数则为1，否则为0。从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即0，这样在运行结束的时候我们即能知道质数的个数。

这种方法包对的的🤗：首先它不会将质数标记成合数；另一方面，当从小到大遍历到数 x 时，倘若它是合数，则它一定是某个小于x的质数y的整数倍，故根据此方法的步骤，我们在遍历到 y 时，就一定会在此时将 x 标记为 isPrime[x]=0。因此，这种方法也不会将合数标记为质数。

当然这里还可以继续优化，对于一个质数 x，如果按上文说的我们从 2x 开始标记其实是多余的，应该直接从 x^2 开始标记，因为 2x,3x,… 这些数一定在 x 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等。🥰

下面是参考代码与一道与埃氏筛有关的LeetCode的题目的题解（好像还有更简单的办法，但是我看不懂一点🥹）。

三、代码

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    // 判断[2,n - 1]的质数个数
    int countPrimes(int n)
    {
        // 假设全部为质数
        vector<int> isPrime(n, 1);
        int ans = 0;
        // 从2开始遍历
        for (int i = 2; i < n; ++i)
        {
            // 如果当前数是质数
            if (isPrime[i])
            {
                // 结果+1
                ans += 1;
                // 将所有i的整数倍i*2,i*3,i*4,...标记为非质数
                if (i * i < n)
                {
                    for (int j = i * i; j < n; j += i)
                    {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }
};

四、参考链接

LeetCode : https://leetcode.cn/problems/count-primes/solutions/507273/ji-shu-zhi-shu-by-leetcode-solution/