| 1 | #include "prime_sieve.cpp" |
| 2 | unordered_map<ll,ll> primepi(ll n) { |
| 3 | #define f(n) (1) |
| 4 | #define F(n) (n) |
| 5 | ll st = 1, *dp[3], k = 0; |
| 6 | while (st*st < n) st++; |
| 7 | vi ps = prime_sieve(st); |
| 8 | ps.push_back(st+1); |
| 9 | rep(i,0,3) dp[i] = new ll[2*st]; |
| 10 | ll *pre = new ll[(int)size(ps)-1]; |
| 11 | rep(i,0,(int)size(ps)-1) |
| 12 | pre[i] = f(ps[i]) + (i == 0 ? f(1) : pre[i-1]); |
| 13 | #define L(i) ((i)<st?(i)+1:n/(2*st-(i))) |
| 14 | #define I(l) ((l)<st?(l)-1:2*st-n/(l)) |
| 15 | rep(i,0,2*st) { |
| 16 | ll cur = L(i); |
| 17 | while ((ll)ps[k]*ps[k] <= cur) k++; |
| 18 | dp[2][i] = k, dp[1][i] = F(L(i)), dp[0][i] = 0; } |
| 19 | for (int j = 0, start = 0; start < 2*st; j++) { |
| 20 | rep(i,start,2*st) { |
| 21 | if (j >= dp[2][i]) { start++; continue; } |
| 22 | ll s = j == 0 ? f(1) : pre[j-1]; |
| 23 | int l = I(L(i)/ps[j]); |
| 24 | dp[j&1][i] = dp[~j&1][i] |
| 25 | - f(ps[j]) * (dp[~min(j,(int)dp[2][l])&1][l] - s); |
| 26 | } } |
| 27 | unordered_map<ll,ll> res; |
| 28 | rep(i,0,2*st) res[L(i)] = dp[~dp[2][i]&1][i]-f(1); |
| 29 | delete[] pre; rep(i,0,3) delete[] dp[i]; |
| 30 | return res; } |
| 31 | // vim: cc=60 ts=2 sts=2 sw=2: |