私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「プライム・ホッパー」（CodeIQ）を参照してください。
ある素数に対し、次の変換１と２のいずれかを適用し、新たな素数を作ります。
変換１：元の数の右または左に1～9のいずれかの数字一つをつなげる。
（例：2→23、13→139、3→13、29→229）
変換２：元の数の右端または左端の数字一つを取り除く。
（元の数が 2 桁以上の場合のみ。例：31→3、673→67、23→3、673→73）
例えば 7→227、17→37 は有効な変換ではありません。
また 103→03 のように、先頭に 0 のつく数への変換はできません。
さて、素数 p と q（p ＜ q）が与えられたときに、素数 p から始めて、変換１または２により q 以下の素数を作るということを繰り返し行い、最小の変換回数で q を作ることを考えましょう。
p＝5，q＝67 のときの一例を示します。
計 5 回の変換で 67 に変換できます。途中の数がいずれも 67 以下の素数であることに注意して下さい。
なお必ずしも変換１と２の両方を行う必要はありません。
5 → 53 → 3 → 37 → 7 → 67
素数 p, q に対し、p から始めて q を作るときの最小の変換回数を F(p, q) と定義します。
そのような作り方が存在しない場合は F(p, q) ＝ -1 と定義します。
例えば F(5, 67) = 5，F(3, 29) = 3，F(5, 541) = 10，F(3, 7) = -1 です。
標準入力から、半角空白区切りで素数 p, q（p ＜ q かつ q ≦ 105）が与えられます。 標準出力に F(n) の値を出力するプログラムを書いてください。
Rubyで解答しています。
#!/usr/bin/ruby
require 'prime'
def addLR(v, ed)
ret = []
for i in 1..9
l = i * (10**v.to_s.size) + v # 左につける
if (l <= ed) && l.prime? then ret << l end
r = v * 10 + i # 右につける
if (r <= ed) && r.prime? then ret << r end
end
return ret
end
def removeLR(v)
ret = []
x = 10**(v.to_s.size-1)
l = v - ((v / x) * x)
if (l != 0) && (l.to_s.size == v.to_s.size-1) && l.prime? then ret << l end
r = v / 10
if (r != 0) && r.prime? then ret << r end
return ret
end
def solve(st, ed)
memo = [[st]]
i = 0
ret = -1
begin
i += 1
memo << []
bef = memo[i-1]
for v in bef
memo[i] += addLR(v, ed)
memo[i] += removeLR(v)
end
memo[i].uniq!
if i >= 2 then memo[i] -= memo[i-2] end
if memo[i].include?(ed) then
ret = i
break
end
end while !memo[i].empty?
return ret
end
# main
while line = gets
line.strip!
if line.empty? then next end
st,ed = line.split.map{|a| a.to_i}
p solve(st, ed)
end
問題の通りに素直に実装すればできる問題です。
特にRubyではprimeライブラリに素数判定が存在するので容易に実装できます。
問題の通りに、pから初めて左右に数字を付け加えるか、取り除いて素数を作るということを繰り返します。これ自体はそれほど難しいプログラムではないはずです。ただし同じ数を繰り返して終わらなくなる場合があるので注意が必要です。例えば、17→7→17→7…のようになる場合があるのでこれを排除しなければなりません。
元の数の左右に1〜9を付け加えて新たな素数を作ります。
左につける場合は1〜9に10元の数の桁を掛けた値を加えればできます。右につける場合は元の数を10倍して1〜9を足せばOKです。
少し気にしておいて損はないのが9行目及び12行目の条件で、素数判定を最後の条件にしている部分です。ほとんどの場合素数判定は呼び出されるので大きな効果はありませんが、（おそらく）素数判定は思い処理なので後の方で判定する方が処理が速くなります。
元の数の数字を取り除いて加えて新たな素数を作ります。
左を取り除く場合、元の数の最上位桁だけの数を下の数から引けばできます。Rubyは整数/整数は整数になるので21〜22行目の処理でこれを実現できます。例えば293ならx = 10**(3-1) = 100で、293 - ((293/100) * 100)ですが(293/100)が2になるので結果は93になります。
23行目の(l.to_s.size == v.to_s.size-1)は先頭が0でないことのチェックです。先頭が0でなければ新たに作った値は下の数より1桁小さいはずなのでそれをチェックします。
右側の数を除くのは簡単で単に10で割ればOKです。
考え方の通りに実装します。
memoは途中過程で作成した数のリストを回数ごとに保持しておきます。
memo[0]は初期値でpを入れておきます。
あとはqができるまでひたすらaddLR()とremoveLR()を呼び出して数を作り続ければ良いのですが、pからqを作れない場合があります。この場合、下の数を処理した結果できる素数の数が0になるのでそれをループの終了条件にします（54行目）。
少なくとも1回は処理するということでdo-whileにしましたが、あまり関係なかったです。
まず、ループの最初にカウンタを進め（37行目）、今回作成する値を保持する領域を追加します（38行目）。
39行目の処理は消し忘れです。
前回の値全てに対してaddLR()、removeLR()を適用して素数リストをmemo[]に追加します（41〜44行目）。
作った値の重複を削除し（46行目）、前々回に出現した値を排除します（47行目）。前々回に出現した値を排除しないと無限ループに陥ります。
作った数字の中にqがあれば終わりです（49〜52行目）。
最終的にループカウンタを印字すれば結果になります。
★★★でしたがこの出題者にしては容易な問題という印象でした。
とはいえ、無限ループに陥って再提出しているのですが。
数値の操作は文字列でやった方が簡単かもしれません。私は最初がC/C++のプログラマなのでなるべく数値で計算したくなってしまいますが。
ちなみに素数判定が重くて性能が足りなかった場合のためにもう一つ方法を考えました（実装はしていません）。
100000以下の素数表を桁数ごとに最初に作ってしまって、元の数±1桁の数から選ぶという方法です。直感的にはこちらの方が早いと思うのですがどうでしょうか？