Trong một chuyến thám hiểm kim tự tháp bí ẩn, nhà khảo cổ học Tùng tìm thấy một cánh cửa đá khổng lồ chắn lối vào kho báu. Trên cánh cửa có khắc hai số nguyên \(a\) và \(b\). Theo văn bia cổ, để mở được cửa, Tùng cần phải tính toán chính xác có bao nhiêu Số Thần Thánh nằm trong đoạn từ \(a\) đến \(b\).
Một số tự nhiên được gọi là Số Thần Thánh nếu nó thỏa mãn hai điều kiện sau:
- Bản thân nó là một số nguyên tố.
- Tổng các chữ số của nó cũng là một số nguyên tố.
Hãy giúp Tùng tìm ra con số bí mật này để mở cánh cửa kho báu.
Input
Vào từ tệp văn bản MATMA.INP gồm một dòng duy nhất chứa hai số nguyên \(a\) và \(b\) (\(1 \le a \le b \le 10^7\)).
Output
Ghi ra tệp văn bản MATMA.OUT một số nguyên duy nhất là số lượng "Số Thần Thánh" trong đoạn \([a, b]\).
Example
Test 1
Input
10 30Output
3Note
Giải thích: Trong đoạn \([10, 30]\), các số nguyên tố là: \(11, 13, 17, 19, 23, 29\).
- \(11\): Tổng chữ số \(1+1=2\) (là số nguyên tố) \(\rightarrow\) Thỏa mãn.
- \(13\): Tổng chữ số \(1+3=4\) (không phải nguyên tố) \(\rightarrow\) Loại.
- \(17\): Tổng chữ số \(1+7=8\) (không phải nguyên tố) \(\rightarrow\) Loại.
- \(19\): Tổng chữ số \(1+9=10\) (không phải nguyên tố) \(\rightarrow\) Loại.
- \(23\): Tổng chữ số \(2+3=5\) (là số nguyên tố) \(\rightarrow\) Thỏa mãn.
- \(29\): Tổng chữ số \(2+9=11\) (là số nguyên tố) \(\rightarrow\) Thỏa mãn.
Vậy có 3 số thỏa mãn là \(11, 23, 29\).
Scoring
- Subtask 1 (\(30\%\) số điểm): \(1 \le a \le b \le 100\).
- Subtask 2 (\(30\%\) số điểm): \(1 \le a \le b \le 10^4\).
- Subtask 3 (\(40\%\) số điểm): Không có ràng buộc gì thêm.
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.