https://www.acwing.com/solution/content/68127/
这篇题解挺好的
1、（朴素做法）

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int n;
int cnt;
bool st[N];
int prime[N];
int get_prime(int x)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])prime[cnt++]=i;//prime存质数
        for(int j=i+i;j<=n;j+=i)st[j]=true;//把i的倍数全部筛掉，全部筛完后，剩下的都是质数
    }

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

2.（埃氏筛法）

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int n;
int cnt;
bool st[N];
int prime[N];
int get_prime(int x)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
        prime[cnt++]=i;//prime存质数
        for(int j=i+i;j<=n;j+=i)st[j]=true;//进入if语句,只筛质数的倍数
        }
    }

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

3.（线性筛法）

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int n;
int cnt;
bool st[N];
int prime[N];
int get_prime(int x)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])prime[cnt++]=i;
        for(int j=0;prime[j]<=n/i;j++)
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0)break;
        }
    }

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