Untitled
unknown
plain_text
21 days ago
1.0 kB
2
Indexable
Never
#include <iostream> #include <vector> using namespace std; void sieve_of_eratosthenes(int max_limit, vector<bool> &is_prime, vector<int> &prime_count) { is_prime[0] = is_prime[1] = false; for (int i = 2; i <= max_limit; i++) { is_prime[i] = true; } for (int i = 2; i * i <= max_limit; i++) { if (is_prime[i]) { for (int j = i * i; j <= max_limit; j += i) { is_prime[j] = false; } } } prime_count[0] = 0; for (int i = 1; i <= max_limit; i++) { prime_count[i] = prime_count[i - 1] + (is_prime[i] ? 1 : 0); } } int main() { int q; cin >> q; const int MAX_LIMIT = 2000000; vector<bool> is_prime(MAX_LIMIT + 1); vector<int> prime_count(MAX_LIMIT + 1); sieve_of_eratosthenes(MAX_LIMIT, is_prime, prime_count); while (q--) { int l, r; cin >> l >> r; int count = prime_count[r] - prime_count[l - 1]; cout << count << endl; } return 0; }
Leave a Comment