Prime in range (mảng cộng dồn)
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Cho Q truy vấn, mỗi truy vấn yêu cầu bạn in ra số lượng số nguyên tố từ L tới R.
Định dạng đầu vào: Dòng đầu tiên là Q; Q dòng tiếp theo mỗi dòng là 2 số L, R
Ràng buộc: 1<=Q<=10^4; 1<=L,R<=10^6.
Định dạng đầu ra: Với mỗi truy vấn in ra số lượng số nguyên tố trong đoạn [L, R]
Input:
9
3 17
1 11
2 18
1 15
4 15
4 18
4 17
2 12
4 20
Output:
6
5
7
6
4
5
5
5
6
Bình luận
include <bits/stdc++.h>
using namespace std; const int N = 1000000; bool isPrime[N+1]; int primeCount[N+1]; int main() { ios::syncwithstdio(false); cin.tie(NULL); for (int i = 2; i <= N; i++) isPrime[i] = true; for (int i = 2; i * i <= N; i++) { if (isPrime[i]) { for (int j = i * i; j <= N; j += i) isPrime[j] = false; } } for (int i = 1; i <= N; i++) { primeCount[i] = primeCount[i-1] + (isPrime[i] ? 1 : 0); } int Q; cin >> Q; while (Q--) { int L, R; cin >> L >> R; if (L > R) swap(L, R); cout << primeCount[R] - primeCount[L-1] << "\n"; }
} code dung