SPOJ PPATH，轉換給定的4位質到其他4位質

Question

在SPOJ問題PPATH，我們給出了兩個四位數字的質數，我們必須進行轉換，以儘可能少的步驟，第一任到第二個通過一次更改一個數字，每一步都應該是質數。如果素數不能以上述方式轉換，我們必須輸出'IMPOSSIBLE'。

然而，對不可能的情況甚至沒有考慮的問題的解決方案已被接受，這導致人們猜測每個四位數的素數可以以指定的方式轉換爲任何其他四位數的素數。我無法證明這一點。這是真的嗎？我們如何才能正式證明？此外，是否有一個通用的結果爲n位數的素數？

Answer 1

對於四位數字這可以通過詳盡的程序進行驗證，但對於n位，我們將不得不在理論上證明這一點。

Answer 2

，所以你有頂點作爲主要的四位數字號碼和連接這1位不同的兩個數的邊緣的無向圖。要求您查找從一個頂點到另一個頂點的最近路徑。如果你不能找到這樣的路徑，將會產生不可能的結果。這意味着該圖有多個連接組件。如果你證明這個圖有一個連通的組件，它將保證路徑的存在。

我不知道如何來證明它在正式的方式，但它是很容易檢查，如果上述圖形只有一個連接部件。您可以編寫一個算法，其結果可以解釋爲4位圖的特定情況的證明。