Cho hai số nguyên tố khác nhau có bốn chữ số.
Người ta cho rằng hoàn toàn có thể biến đổi từ số này thành số kia sau một số
bước theo quy tắc: Tại mỗi bước ta chỉ thay đổi một chữ số trong số trước đó
sao cho số tạo được trong mỗi bước đều là một số nguyên tố có bốn chữ số. Một
cách biến đổi như vậy gọi là một “đường nguyên tố”.
Bài toán đặt ra là với một cặp số nguyên tố
đầu vào, hãy tính ra số bước của đường nguyên tố ngắn nhất. Giả sử đầu vào là
hai số 1033 và 8179 thì đường nguyên tố ngắn nhất sẽ có độ dài là 6 với các
bước chuyển là: 1033 -> 1733
-> 3733 -> 3739 -> 3779 -> 8779 -> 8179
Dữ liệu vào: Từ tệp văn bản
DUONGNT.INP
Gồm 2 số nguyên tố u và v, mỗi số có đúng 4
chữ số cõ nghĩa.
Dữ liệu ra: ghi vào tệp văn bản
DUONGNT.OUT
Số bước của đường nguyên tố ngắn nhất của 2
số nguyên u và v.
Ví dụ:
DUONGNT.INP
|
DUONGNT.OUT
|
1033 8179
|
6
|
