Biểu thức có giá trị là số nguyên tố
Xem dạng PDF
Gửi bài giải
Điểm:
100,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
125M
Input:
stdin
Output:
stdout
Tác giả:
Người đăng:
Dạng bài
Đề bài: Biểu thức có giá trị là số nguyên tố
An 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 tuyển hôm nay được thầy giáo ra cho đội tuyển như sau:
Cho số nguyên dương ~n~ (~1 \leq n \leq 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 \leq x, y \leq n~
~p~ là một số nguyên tố.
Dữ liệu: Cho trong tập tin BIEUTHUCNT.INP gồm một số nguyên dương ~n~.
Kết quả: Ghi ra tập tin BIEUTHUCNT.OUT gồm một số nguyên dương 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 = 1 + 2 \times 1 = 3~ • ~(1,2)~, ~p = 1 + 2 \times 2 = 5~ • ~(1,3)~, ~p = 1 + 2 \times 3 = 7~ • ~(3,1)~, ~p = 3 + 2 \times 1 = 5~ • ~(3,2)~, ~p = 3 + 2 \times 2 = 7~ • ~(3,4)~, ~p = 3 + 2 \times 4 = 11~ |
Giới hạn:
Có 80% số test ứng với ~n \leq 10^3~
Có 20% số test còn lại ứng với ~10^3 < n \leq 10^6~
Bình luận