DDOSvoid's Blog

Loj 6235 区间素数个数

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目描述

https://loj.ac/p/6235

简要题意：求 $1\sim n$ 的素数个数

$n\le 10^{11}$

Solution

同样考虑 $Min\underline{}25$ 筛，我们只需要令 $f(x)=1$，这显然是个完全积性函数

因为最后我们只要 $\sum f(p)$，所以我们只需要计算 $g(n,|P|)$ 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cmath>
#define ll long long
#define maxn 1000010
using namespace std;

ll n; 

int pri[maxn], cnt; bool isp[maxn]; ll sp[maxn];
void init_isp(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, sp[cnt] = cnt;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
        }
    }
}

ll id1[maxn], id2[maxn]; int Sn;
inline int get_id(ll x) { return x <= Sn ? id1[x] : id2[n / x]; }

ll g[maxn], w[maxn]; int num;
void init_min25(ll n) {
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l); w[++num] = n / l; 
        g[num] = n / l - 1;
        if (w[num] <= Sn) id1[w[num]] = num;
        else id2[n / w[num]] = num;
    }
    for (int i = 1; i <= cnt; ++i)
        for (int j = 1; j <= num && 1ll * pri[i] * pri[i] <= w[j]; ++j) 
            g[j] -= g[get_id(w[j] / pri[i])] - sp[i - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; Sn = sqrt(n); init_isp(Sn); init_min25(n);
    cout << g[get_id(n)];
    return 0;
}