标程：【模板】线性素数筛法

#include <iostream>
#include <cstring>
using namespace std;
int tot, n;
int prime[2500000];
bool isp[40000005];

void find_prime() {
    memset(isp + 2, 1, sizeof(isp) - 2);
    for (register int i = 2; i <= n; ++i) {
        if (isp[i]) {
            prime[++tot] = i;
        }
        for (register int j = 1; j <= tot && i * prime[j] <= n; ++j) {
            isp[i * prime[j]] = false;
            if (i % prime[j] == 0)
                break;
        }
    }
    return;
}

int main() {
    cin >> n;
    find_prime();
    cout << tot << endl;
    return 0;
}