题目描述

给你一个数 $n$，请你求出区间 $[2,n]$ 中共有多少个质数。

样例

输入样例1：

8

输出样例1：

4

算法1 埃氏筛

基本思路

朴素的埃氏筛很简单。用区间 $[2,n]$ 中的每一个数去筛掉它的倍数即可。

bool st[N]; //st[i]记录i是不是合数

int cntprime(int n) {
    int cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) //st[i]不是合数
            cnt ++;
        for (int j = i+i; j <= n; j += i) //筛去i的所有倍数
            st[j] = 1;
    }
    return cnt;
}

我们如何求它的复杂度呢？

这个代码执行了 $(n/2+n/3+n/4+…+n/n)$ 次。我们有：

$$\lim_{n \to \infty} \left (1/1+1/2+1/3+…+1/n\right )=\ln n+\gamma $$

其中，$\ln n$ 表示以 $e$ 为底的自然对数，即 $\ln n=\log_e n$，$\gamma$ 是欧拉常数，约等于 $0.577$.

而 ${\small n/2+n/3+n/4+…+n/n=n(1/1+1/2+1/3+…+n/n)-n=n\ln n+\gamma\times n-n}$.

这个结果可以粗略地看为 $n\ln n$.

而 $\ln n=\log_e n<\log_2 n$，所以朴素的埃氏筛的时间复杂度是 $O(n\log n)$.

但其实朴素的埃氏筛有一点浪费了时间：它会筛去合数的倍数。例如，$2$ 已经筛掉了 $8$ 和 $12$，但 $4$ 还要再筛它们一遍，所以我们只需要筛质数的倍数即可。

给出要筛数值的范围 $n$，找出以内的素数。先用 $2$ 去筛，即把 $2$ 留下，把 $2$ 的倍数剔除掉；再用下一个质数，也就是 $3$ 筛，把 $3$ 留下，把 $3$ 的倍数剔除掉；接下去用下一个质数 $5$ 筛，把 $5$ 留下，把 $5$ 的倍数剔除掉；不断重复下去……

参照上面的方法，我们可以写出改进版的埃氏筛的算法：

bool st[N]; //st[i]记录i是不是合数

int cntprime(int n) {
    int cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) { //st[i]不是合数
            cnt ++;
            for (int j = i+i; j <= n; j += i) //筛去i的所有倍数
                st[j] = 1;
        }
    }
    return cnt;
}

根据素数定理，可知区间 $[1,n]$ 内大约有 $\dfrac{n}{\ln n}$ 个质数。

而 $n\ln n / \ln n=n$.

所以改进版的埃氏筛的时间复杂度大约是 $O(n)$.

但实际上，改进版的埃氏筛的时间复杂度是 $O(n\log\log n)$，但 $\log\log n$ 可以粗略地看作一个常数。例如，当 $n=2^{32}$ （unsigned int 的最大值加上 $1$ ）时，$\log\log n=\log 32=5$.

完整代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1000010;

bool st[N];

int cntprime(int n) {
    int cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) {
            cnt ++;
            for (int j = i+i; j <= n; j += i)
                st[j] = 1;
        }
    }
    return cnt;
}

int main() {
    int n;
    scanf("%d", &n);
    int ans = cntprime(n);
    printf("%d", ans);
    return 0;
}

算法2 线性筛

基本思路

尽管改进版的埃氏筛已经很快了，但仍然有一个不足。例如：对于 $15$，$3$ 会筛掉它，但 $5$ 也会筛掉它。线性筛在埃氏筛的基础上进行了改进，只用一个数的最小质因子筛去它。

首先定义一个 bool 类型数组 $st$（ $st_i$ 表示 $i$ 是不是合数），一个 int 类型数组 $pr$ （ $pr_i$ 表示第 $i+1$ 个质数） 和计数器 $cnt$，表示区间 $[2,n]$ 之间质数的数量。

int pr[N], cnt;
bool st[N];

然后遍历区间 $[2,n]$，如果 $st_i = 0$，说明 $i$ 是质数，将其存储到 $pr$ 数组中。

for (int i = 2; i <= n; ++i) {
    if (!st[i])
        pr[cnt ++] = i;

     //... 
}

随后，从第一个质数开始，筛去质数与 $i$ 的乘积，直到 $i$ 第一次被一个质数 $pr_j$ 整除。此时，$pr_j$ 是 $i$ 的最小质因数，跳出循环。

for (int j = 0; pr[j] <= n/i; ++j) {
    st[pr[j] * i] = 1;
    if (i % pr[j] == 0)
        break;
}

顾名思义，线性筛的复杂度是线性的，即 $O(n)$.

完整代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1000010;

int pr[N], cnt;
bool st[N];

void cntprime(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!st[i])
            pr[cnt ++] = i;

        for (int j = 0; pr[j] <= n/i; ++j) {
            st[pr[j] * i] = 1;
            if (i % pr[j] == 0)
                break;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    cntprime(n);
    printf("%d", cnt);
    return 0;
}