Loj 6235 区间素数个数

题目描述

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;
}