loj#6235. 区间素数个数(min25筛)

题意

sol

min25筛的板子题，直接筛出\(g(n, \infty)\)即可

筛的时候有很多trick，比如只存\(\frac{n}{x}\)的值，第二维可以滚动数组滚动掉

#include<bits/stdc++.h>
#define ll long long
//#define int long long  
using namespace std;
const int maxn = 2e6 + 10;
int lim, vis[maxn], prime[maxn], tot;
ll n, g[maxn], id[maxn], cnt, pos1[maxn], pos2[maxn];
void get(int n) {
    vis[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!vis[i]) prime[++tot] = i;
        for(int j = 1; j <= tot && i * prime[j] <= n; j++) {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j])) break;
        }
    }
}
ll get(ll x) {
    return x <= lim ? pos1[x] : pos2[n / x];
}
signed main() {
    cin >> n; lim = sqrt(n);
    get(lim);
    for(ll i = 1, j; i <= n; i = n / j + 1) {
        j = n / i; id[++cnt] = j; g[cnt] = id[cnt] - 1;
        j <= lim ? pos1[j] = cnt : pos2[n / j] = cnt;;
    }
    for(int j = 1; j <= tot; j++) 
        for(ll i = 1; 1ll * prime[j] * prime[j] <= id[i]; i++) 
            g[i] -= g[get(id[i] / prime[j])] - (j - 1);
    cout << g[1];
    return 0;
}