Đếm số nguyên tố
Xem PDF
Điểm:
400 (p)
Thời gian:
2.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Hôm nay coder top 1 thế giới nhận lời thách đấu của coder thứ 7 tỉ thế giới solo giải 1 bài toán do giáo sư đưa ra.
Bài toán là cho 2 số tự nhiên \(l,r\). Hãy đếm số lượng số nguyên tố giữa chúng.
loay hoay mãi mà vẫn chưa nghĩ ra cách làm trong khi đã sắp xong, các bạn hãy giúp chiến thắng trong cuộc solo này nhé. Nếu giải được thì sẽ chia 1 nửa phần thưởng của cuộc solo này cho các bạn đó !
- Yêu cầu: đếm số lượng số nguyên tố trong đoạn \([l,r]\)
Input
- Dòng đầu tiên chứa số nguyên dương \(q\) là số đoạn \([l,r]\)
- \(q\) dòng tiếp theo mỗi dòng chứa \(2\) số nguyên dương \(l\) và \(r\)
Output
- Gồm \(q\) dòng, dòng thứ \(i\) ghi một số là số các số nguyên tố trong đoạn \([l,r]\) thứ \(i\) đã cho.
Constraints
- \(1 \leq l,r \leq 2 \times 10^8\)
- \(1 \leq q \leq 10^5\)
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(q \leq 10^3\), \(l\) và \(r \leq 10^7\)
- Subtask \(2\) (\(50\%\) số điểm): \(q \leq 10^5\), \(l\) và \(r \leq 2 \times 10^8\)
Example
Test 1
Input
1
2 5 Output
3
Bình luận
sau bao nỗ lực tránh rte và ole, mình nhận ra sàng thường nhưng cải tiến 6k +- 1 là ac:))
-
2
SPyofgame
9:35 p.m. 26 Tháng 9, 2021
-
2
VoBaThongL921
6:59 a.m. 27 Tháng 9, 2021
-
2
SPyofgame
11:51 a.m. 2 Tháng 10, 2021
-
2
VoBaThongL921
1:10 p.m. 2 Tháng 10, 2021
-
4
SPyofgame
2:57 p.m. 3 Tháng 10, 2021
-
2
VoBaThongL921
4:31 p.m. 3 Tháng 10, 2021
-
2
ap
9:34 a.m. 28 Tháng 11, 2021
-
3
VoBaThongL921
9:38 a.m. 28 Tháng 11, 2021
-
-3
dattuan16_05_07
3:45 p.m. 10 Tháng 3, 2022
-
-3
NMK_hacker_123
4:02 p.m. 10 Tháng 3, 2022
-
-2
Nguyễn_Minh_Khang21L7
8:01 p.m. 30 Tháng 11, 2021
←
đã chỉnh sửa
→
5 bình luận nữaBạn muốn cải tiến thêm mà không quá phức tạp thì có thể xem ở đây nhé UwU Sieving Benchmark
được idol rep luôn:) cảm ơn anh OwO
idol gì thằng gà như mình hả bạn 🙁
Thôi anh ơi khiêm tốn quá đâu có tốt:>
Theo anh thấy thì áp dụng thuyết tương đối của Einstein ta có số người có quan điểm rằng anh gà cao hơn nhiều OwO
Nói chuyện với idol đau đầu qué:) Thuyết tương đối của Einstein là gì vậy ạ, em ngu hóa học nên không biết ạ:<
lý mà:)
burh điểm lý tôi 2.0 có vấn đề zì ko:((
sao bữa tôi hỏi ông hs gì thì ông bảo giỏi mà sao lại 2.0 lí đc(.___.)
thì do mấy con 15' miệng hay giữa kì kéo con 2 lên đc đtb 6,6 :))
ah Thông 2 điểm lý à :))