Elearning CodePath – CTP Online Judge

Số Nguyên Tố Tốt Hơn

GOODPRIME

🟢 Easy #General #Math #Number Theory #Optimization

### 📌 Thông tin chung

---
### 📝 Định nghĩa

Cho hai số nguyên tố $P_1$ và $P_2$. Số $P_1$ được gọi là **số nguyên tố tốt hơn** $P_2$ nếu thỏa mãn điều kiện ưu tiên sau:

1.  **Tổng bình phương các chữ số** của $P_1$ (trong hệ cơ số 10) **lớn hơn** tổng bình phương các chữ số của $P_2$.
2.  HOẶC các tổng bình phương này **bằng nhau** nhưng $P_1 < P_2$.

Ta định nghĩa hàm $S(P)$ là tổng bình phương các chữ số của $P$:
$S(P) = \sum_{d \in \text{digits}(P)} d^2$
$P_1$ tốt hơn $P_2$ nếu:
$(S(P_1) > S(P_2)) \quad \text{HOẶC} \quad (S(P_1) = S(P_2) \land P_1 < P_2)$

Yêu cầu: Cho hai số nguyên $A$ và $B$. Hãy tìm số nguyên tố tốt nhất (Best Prime) trong khoảng $[A, B]$. Số nguyên tố tốt nhất là số nguyên tố $P_{\text{best}}$ sao cho mọi số nguyên tố $P'$ khác trong đoạn $[A, B]$, $P_{\text{best}}$ đều tốt hơn $P'$.

Quy ước: Nếu trong khoảng $[A, B]$ không có số nguyên tố nào thì đưa ra số $-1$.

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

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

* Một dòng chứa hai số nguyên $A$ và $B$.

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

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

Ghi ra file `GOODPRIME.OUT` kết quả tìm được (số nguyên tố tốt nhất hoặc $-1$).

---
### ✨ Ví dụ

| Input (`GOODPRIME.INP`) | Output (`GOODPRIME.OUT`) |
| :--- | :--- |
| `20039 20704` | `20599` |

---
### 🏷 Subtasks

Bài toán có giới hạn $B \le 10^6$. Việc sàng số nguyên tố và tính tổng bình phương chữ số là khả thi.

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

---

✅ Đã AC: 0 / 0 submissions