线性筛和埃氏筛

线性筛：

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<unordered_map>
#include<map>
using namespace std;
#define LL  long long
const int N = 1e6+1000;
const long long  mod = 1e9 + 7;
#define  rep(i,a,b) for (int i = a; i <= b; i++) 
#define per(i, a, b) for(int  i=a;i>=b;i--)
int n,cnt;
int a[N],x,su[N];
unordered_map<int, int> p;
void into()
{
    a[0] = a[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!a[i])
            su[++cnt] = i;
        for (int j = 1; su[j] <= n / i; j++)
        {
            a[su[j] * i] = 1;
            if (i % su[j] == 0) break;
        }
        
    }
}
int main()
{   
    cin >>n;
    into();
    cout << cnt << endl;
    return 0;
}

埃氏筛：

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<unordered_map>
#include<map>
using namespace std;
#define LL  long long
const int N = 1e5 + 1000;
const long long  mod = 1e9 + 7;
#define  rep(i,a,b) for (int i = a; i <= b; i++) 
#define per(i, a, b) for(int  i=a;i>=b;i--)
int n, cnt;
int su[N], a[N], x, flag = 0;
unordered_map<int, int> p;
void into()
{
    a[0] = a[1] = 1;
    rep(i, 1, N)
    {
        if (a[i]) continue;
        su[++cnt] = i;
        p[i] = 1;
        for (int j = 2 * i; j <= N; j += i)
            a[j] = 1;
    }
}
int main()
{
    into();
    return 0;
}