题目描述
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; }
|