/* (q,),*e=[[*map(int,s.split())]for s in open(0)] def spf(n): spf=[*range(n+1)] for i in range(2,n+1): for j in range(i*2,n+1,i): spf[j]=i return spf s=spf(10**6) for i in range(10**6+1): if s[i]==i: s[i]=0 #https://tjkendev.github.io/procon-library/python/range_query/merge-sort-tree.html from bisect import bisect from heapq import merge # count elements A_i s.t. A_i <= k for i in [l, r) def query1(N0, data, l, r, k): L = l + N0; R = r + N0 s = 0 while L < R: if R & 1: R -= 1 s += bisect(data[R-1], k-1) if L & 1: s += bisect(data[L-1], k-1) L += 1 L >>= 1; R >>= 1 return s N=len(s) A=s[:] N0 = 2**(N-1).bit_length() data = [None]*(2*N0) for i, a in enumerate(A): data[N0-1+i] = [a] for i in range(N, N0): data[N0-1+i] = [] for i in range(N0-2, -1, -1): *data[i], = merge(data[2*i+1], data[2*i+2]) for l,r in e: if l==1: ans=1 else: ans=query1(N0,data,l,r+1,l) print(ans) */ #include using namespace std; vector spf(int n) { vector spf(n+1); iota(spf.begin(), spf.end(), 0); for (int i = 2; i <= n; ++i) { for (int j = i*2; j <= n; j += i) { spf[j] = i; } } return spf; } int query1(int N0, vector> &data, int l, int r, int k) { int L = l + N0, R = r + N0; int s = 0; while (L < R) { if (R & 1) { --R; s += upper_bound(data[R-1].begin(), data[R-1].end(), k-1) - data[R-1].begin(); } if (L & 1) { s += upper_bound(data[L-1].begin(), data[L-1].end(), k-1) - data[L-1].begin(); ++L; } L >>= 1; R >>= 1; } return s; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; vector> e(q); for (int i = 0; i < q; ++i) { cin >> e[i].first >> e[i].second; } int MAX = 1e6; vector s = spf(MAX); for (int i = 0; i <= MAX; ++i) { if (s[i] == i) s[i] = 0; } int N = s.size(); int N0 = 1; while (N0 < N) N0 <<= 1; vector> data(2*N0); for (int i = 0; i < N; ++i) { data[N0-1+i] = {s[i]}; } for (int i = N; i < N0; ++i) { data[N0-1+i] = {}; } for (int i = N0-2; i >= 0; --i) { vector &left = data[2*i+1], &right = data[2*i+2]; data[i].resize(left.size() + right.size()); merge(left.begin(), left.end(), right.begin(), right.end(), data[i].begin()); } for (auto [l, r] : e) { int ans; if (l == 1) { ans = 1; } else { ans = query1(N0, data, l, r+1, l); } cout << ans << '\n'; } }