Bài 4. SỐ SIÊU NGUYÊN TỐ (5,0 điểm; Đề HSG9 tỉnh Gia Lai 2025-2026)

Một số tự nhiên lớn hơn 10 được gọi là số siêu nguyên tố nếu cứ xóa bỏ chữ số hàng đơn vị của số đó ta luôn được một số mới là số nguyên tố. Ví dụ số 293 là số siêu nguyên tố vì 293, 29, 2 là các số nguyên tố. Số 17 không phải số siêu nguyên tố vì 1 không phải số nguyên tố.

Yêu cầu: Cho hai số nguyên dương a và b (a ≤ b). Đếm số lượng số siêu nguyên tố trong phạm vi từ a tới b.

Dữ liệu vào: Từ tệp BAI4.INP gồm hai số nguyên dương a và b (a ≤ b ≤ 10¹²) cách nhau một khoảng trống.

Dữ liệu ra: Ghi ra tệp BAI4.OUT số lượng số siêu nguyên tố tìm được.

Ví dụ:

Giải thích:

• Trong ví dụ 1, các số siêu nguyên tố là 23, 29, 31
• Trong ví dụ 2, các số siêu nguyên tố là 233, 239, 293, 311

Ràng buộc:

• Có 15% test tương ứng 15% số điểm có a ≤ b ≤ 100
• Có 15% test tương ứng 15% số điểm có a ≤ b ≤ 10000
• Có 30% test khác tương ứng 30% số điểm có a ≤ b ≤ 10⁶
• Có 40% test còn lại tương ứng 40% số điểm không có ràng buộc gì thêm.