Untitled
unknown
plain_text
15 days ago
672 B
2
Indexable
Never
#include <bits/stdc++.h> using namespace std; const int MAXN = 10000000; vector<int> pr(MAXN + 1, 0); vector<int> prime_count(MAXN + 1, 0); void sieve() { pr[0] = pr[1] = 1; for (int i = 2; i * i <= MAXN; i++) { if (pr[i] == 0) { for (int j = i * i; j <= MAXN; j += i) { pr[j] = 1; } } } for (int i = 1; i <= MAXN; i++) { prime_count[i] = prime_count[i - 1] + (pr[i] == 0 ? 1 : 0); } } int main() { sieve(); int q; cin >> q; while (q--) { int L, R; cin >> L >> R; cout << prime_count[R] - prime_count[L - 1] << "\n"; } return 0; }
Leave a Comment