min25筛前n项素数个数的板子

ll s[320010];
ll a[320010];
ll b[320010];
double inv[320010];
inline ll Prime(ll N) {
   
    ll S = sqrt(N);
    for (int i = 1; i <= S; ++i) a[i] = i, s[i] = i, b[i] = N / i, inv[i] = 1.0 / i;
    s[S + 1] = S + 1, s[S + 2] = S + 2;
    for (int p = 2; p <= S; ++p)
        if (a[p] != a[p - 1]) {
   
            for (int i = 1; i * p <= S;)
                if (s[i] == i) {
   
                    b[i] -= b[i * p] - a[p - 1];
                    i += 2;
                } else
                    i = s[i] = s[s[i]];
            ll q = (ll)p * p, Now = N / p;
            int r = q <= S ? S : Now / p;
            for (int i = (S / p + 1) | 1; i <= r;)
                if (s[i] == i) {
   
                    b[i] -= a[(int)(Now * inv[i] + 1E-9)] - a[p - 1];
                    i += 2;
                } else
                    i = s[i] = s[s[i]];
            if (q <= r)
                for (int i = q; i <= r; i += p)
                    if (s[i] == i)
                        s[i] += 2;
            for (int i = S; i >= q; --i) a[i] -= a[(int)(i * inv[p] + 1E-9)] - a[p - 1];
        }
    return b[1];
}

最后函数返回的时候要减去1，因为把1也当作质数做了。。