欧拉筛

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
typedef long long ll;

const int N = 1e6 + 5;

int prime[N];
bool isPrime[N];

void euler() {
    memset(isPrime, 1, sizeof isPrime);
    isPrime[0] = isPrime[1] = 0;

    for (int i = 2; i < N; i++) {
        if (isPrime[i]) prime[++prime[0]] = i;

        for (int j = 1; j <= prime[0] && i * prime[j] < N; j++) {
            isPrime[i * prime[j]] = 0;
            if (i % prime[j] == 0) break;
        }
    }
}

void solve() {
    cout << prime[0] << '\n';
}
    
int main()
{
    IO;
    euler();
    int t = 1;
    while(t--) {
        solve();
    }
    return 0;
}