[loj6235] 区间素数个数

#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

const int maxn = 1000010;

ll n;
int prm[maxn], isnp[maxn], cnt, tot, sqr;
ll val[maxn];
int in1[maxn], in2[maxn];
ll f[maxn];

int (ll x) {
    if (x >= sqr) {
        if (!in1[n/x]) in1[n/x] = ++ tot;
        return in1[n/x];
    } else {
        if (!in2[x]) in2[x] = ++ tot;
        return in2[x];
    }
}

int main() {
    scanf("%lld", &n);
    sqr = int(sqrt(n));
    isnp[1] = 1;
    for (int i = 2; i <= 1000000; i++) {
        if (!isnp[i]) {
            prm[++ cnt] = i;
        }
        for (int j = 1; j <= cnt && prm[j]*i <= 1000000; j++) {
            isnp[i*prm[j]] = 1;
            if (i % prm[j] == 0) break;
        }
    }
    int mx = 0;
    for (ll i = 1; i <= n;) {
        ll nxt = n/(n/i)+1;
        val[getin(n/i)] = n/i;
        i = nxt;
    }
    for (int i = 1; i <= tot; i++) f[i] = val[i]-1;
    int last = 0;
    for (int i = 1; i <= cnt && 1LL*prm[i]*prm[i] <= n; ++ i) {
        last = i;
        for (int j = 1; j <= tot && val[j] >= 1LL*prm[i]*prm[i]; j++) {
            f[j] -= (f[getin(val[j]/prm[i])]-(i-1));
        }
    }
    printf("%lldn", f[getin(n)]);
    return 0;
}