Biểu thức có giá trị là số nguyên tố
Xem dưới dạng PDF
Gửi bài giải
Điểm:
5 (một phần)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
BIEUTHUCNT.INP
Output:
BIEUTHUCNT.OUT
Tác giả:
Kiểu bài tập
karvp cùng các bạn trong đội tuyển Tin học của trường đang học tập tích cực để tham gia một kì thi lập trình danh giá sắp tới. Bài tập ôn luyện hôm nay được thầy giáo ra cho đội tuyển như sau:
Cho số nguyên dương ~n~ (~1 ≤ n ≤ 10^6~).
Xét biểu thức ~p = x + 2y~.
Yêu cầu:
Tìm số lượng cặp số nguyên dương ~(x, y)~ sao cho:
- ~1 ≤ x, y ≤ n~
- ~p~ là một số nguyên tố
Dữ liệu:
Trong tệp văn bản BIEUTHUCNT.INP gồm một số nguyên dương ~n~.
Kết quả:
Ghi ra tệp văn bản BIEUTHUCNT.OUT gồm một số nguyên dương là giá trị của ~s~.
Trong đó ~s~ là số lượng các cặp số nguyên dương ~(x, y)~ thỏa mãn hai điều kiện trên.
Ví dụ:
| BIEUTHUCNT.INP | BIEUTHUCNT.OUT | Giải thích |
| 4 | 6 | Có 6 cặp (x, y) thỏa mãn: (1,1), p = 3 (1,2), p = 5 (1,3), p = 7 (3,1), p = 5 (3,2), p = 7 (3,4), p = 11 |
Giới hạn:
- Có 80% số test ứng với ~n ≤ 10^3~
- Có 20% số test còn lại ứng với ~10^3 < n ≤ 10^6~
Nhận xét
:V