Elearning CodePath – CTP Online Judge

Số Fibonacci Nguyên Tố Nhỏ Hơn P

FIBOP

🟢 Hard #Math #Number Theory

### 📌 Thông tin chung

---
### 📝 Định nghĩa và Bài toán

**Dãy số Fibonacci** ($F_n$) được định nghĩa như sau:
$F_1 = 1, \quad F_2 = 1, \quad F_n = F_{n-1} + F_{n-2} \quad \text{với } n \ge 3$
Tức là dãy số bắt đầu là: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots$

Yêu cầu: Cho số nguyên dương $P$. Hãy xác định số lượng các số $X$ thỏa mãn đồng thời ba điều kiện sau:
1.  $X$ là một số nguyên tố.
2.  $X$ là một số Fibonacci.
3.  $X \le P$.

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

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

* Một dòng duy nhất ghi số nguyên dương $P$.

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

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

Ghi ra file `FIBOP.OUT` một số nguyên duy nhất là số lượng số Fibonacci nguyên tố tìm được.

---
### ✨ Ví dụ

| Input (`FIBOP.INP`) | Output (`FIBOP.OUT`) |
| :--- | :--- |
| `10` | `3` |

Giải thích:
* Dãy Fibonacci $\le 10$: $1, 1, 2, 3, 5, 8$.
* Các số nguyên tố trong dãy này: $2, 3, 5$.
* Số lượng: $3$.

---
### 🏷 Subtasks

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

---

✅ Đã AC: 7 / 17 submissions