线性筛

时间复杂度：$O(n)$

这里只有线性筛，参考了网络里的部分题解，详情见代码吧
觉得看完之后懂了的朋友可以点个赞再走，谢谢大家！

C++ 代码

//线性筛
//https://www.cnblogs.com/zhuohan123/p/3233011.html

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 7;

int cnt;
int prime[N];
bool st[N];

void get_prime(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])                              //如果还没被标记过，就说明这是个质数，就把它加入到队列中
            prime[cnt++] = i;

        for(int j = 0; prime[j] <= n / i; j++)  //确保第j个质数和i相乘不会爆n
        {
            st[prime[j] * i] = true;
            /*
                prime[]数组中的素数是递增的,当i能整除prime[j]，那么i*prime[j+1]这个合数
                肯定被prime[j]乘以某个数筛掉。
                因为i中含有prime[j],prime[j]比prime[j+1]小，
                即i=k*prime[j]，那么i*prime[j+1]=(k*prime[j])*prime[j+1]=k’*prime[j]，
                接下去的素数同理。所以不用筛下去了。
                因此，在满足i%prime[j]==0这个条件之前以及第一次满足改条件时,
                prime[j]必定是prime[j]*i的最小因子。
            */
            if(i % prime[j] == 0)               
                break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_prime(n);
    cout << cnt << endl;
    return 0;
}