Elearning CodePath – CTP Online Judge

Tổng Các Số Nguyên Tố Trong Đoạn [A, B]

SUMPRIME

🟢 Hard #General #Math #Number Theory #Interval

### 📌 Thông tin chung

---
### 📝 Bài toán

Yêu cầu: Cho hai số nguyên dương $A$ và $B$, hãy tính **tổng các số nguyên tố** $P$ nằm trong đoạn $[A, B]$.
$\text{Tổng} = \sum_{P \text{ là số nguyên tố}}^{A \le P \le B} P$

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `SUMPRIME.INP`:

* Dòng đầu tiên: Ghi số nguyên dương $T$ là số lượng các yêu cầu.
* $T$ dòng tiếp theo: Mỗi dòng ghi hai số nguyên dương $A$ và $B$ ($1 \le A \le B \le 10^6$) là một yêu cầu cần phải thực hiện.

Giới hạn:
* $1 \le T \le 10^5$.
* $1 \le A \le B \le 10^6$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `SUMPRIME.OUT` gồm $T$ dòng, mỗi dòng ghi một số nguyên là tổng các số nguyên tố tìm được của câu hỏi tương ứng (theo thứ tự trong file dữ liệu).

---
### ✨ Ví dụ

| Input (`SUMPRIME.INP`) | Output (`SUMPRIME.OUT`) |
| :--- | :--- |
| `2` <br> `1 20` <br> `10 20` | `77` <br> `60` |

Giải thích:
* **Yêu cầu 1 (1, 20):** Các số nguyên tố là $2, 3, 5, 7, 11, 13, 17, 19$. Tổng $= 77$.
* **Yêu cầu 2 (10, 20):** Các số nguyên tố là $11, 13, 17, 19$. Tổng $= 60$.

---
### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $T \le 100$; $B \le 10^3$ | $20\%$ |
| 2 | $T \le 10^4$; $B \le 10^5$ | $30\%$ |
| 3 | $T \le 10^5$; $B \le 10^6$ | $50\%$ |

---

✅ Đã AC: 2 / 11 submissions