ガジェット通信

見たことのないものを見に行こう

数学の問題をプログラミングで解こう!「プライム・ホッパー」問題解説

DATE:
  • ガジェット通信を≫

問題のおさらい

ある素数に対し、次の変換1と2のいずれかを適用し、新たな素数を作ります。

変換1:元の数の右または左に1~9のいずれかの数字一つをつなげる。
(例:2→23、13→139、3→13、29→229)
変換2:元の数の右端または左端の数字一つを取り除く。
(元の数が 2 桁以上の場合のみ。例:31→3、673→67、23→3、673→73)

例えば 7→227、17→37 は有効な変換ではありません。
また 103→03 のように、先頭に 0 のつく数への変換はできません。

さて、素数 p と q(p < q)が与えられたときに、素数 p から始めて、変換1または2により q 以下の素数を作るということを繰り返し行い、最小の変換回数で q を作ることを考えましょう。

p=5,q=67 のときの一例を示します。
計 5 回の変換で 67 に変換できます。途中の数がいずれも 67 以下の素数であることに注意して下さい。
なお必ずしも変換1と2の両方を行う必要はありません。

  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) の値を出力するプログラムを書いてください。

方針

今回は数学というよりもアルゴリズムの問題に近い内容でした。

本問では、素数とその変換の関係を、グラフでとらえることがポイントです。各素数をノード(頂点)とみなし、素数間で変換が可能であればノード間にエッジ(枝)が存在するとみなします。次のようなグラフです。

つまり、本問は、素数 p のノードから始めて、目的の素数 q のノードまで、できるだけ少ない本数のエッジを通ってたどり着く行き方を求めることになります。

そこで有効なのが、幅優先探索のアプローチです。幅優先探索については下記のページなどを参照して下さい。

参考:幅優先探索(Wikipedia)

アルゴリズムは次のようになります。まず、素数 p のノードから始めて、エッジでつながった全てのノードを探索します(1 段目)。エッジでつながったノードとは、p に変換 1 または 2 をほどこして作れる素数のことです。そしてそのノードのそれぞれについて、同様にエッジでつながった全てのノードを探索します(2 段目)。以降、3 段目、4 段目、…と、同じことを繰り返して探索対象のノードを見つけていきます。

実装

実装は少々ややこしいです。まず、本問では素数かどうかの判定を大量に行います。そこでブール変数の配列を用意し、エラトステネスの篩のアルゴリズムで素数の判定表を作りましょう。

参考:エラトステネスの篩(Wikipedia)

次にリストを 2 つ用意します。一方のリストに素数 p を入れておきます。このリストの各要素について、変換で新しい数を作ります。上述の判定表でチェックし、もしこれが素数であれば、もう一方のリストに追加します。これを繰り返せば、素数 p から 1 回の変換でたどり着ける素数の一覧ができ上がります。これらの素数を対象に同じ処理を繰り返せば、2 回の変換でたどり着ける素数の一覧が得られます。以降、同様に 3 回、4 回、5 回、…と、p のノードからたどれる全てのノードを網羅的にループで検査することができます。

目的の素数 q にたどり着いたなら、これまでの繰り返しの数を出力し、ループを抜けましょう。もし q にたどり着くことなくリストが空っぽになってしまったら、q へは到達不可ということで、-1 を出力します。

コードを書く上で、ひとつハマりどころがあります。検査済みの数を別途記録しておき、同じ数を二度以上検査しないようにしましょう。これをしないと、2 つの素数の間を行ったり来たり、無限ループが生じてコードが終了しません。

コード例は以下です(python)。コードをシンプルにするひと工夫として、素数の判定表と検査済みかどうかのチェック表とを別々に作るのではなく、同じ配列(candidates[x])で行っています。

p, q = map(int, raw_input().split())

# candidates[x]: xが素数かつ未探索
candidates = [True] * (q+1)
for i in range(2, q+1):
if candidates[i] == False:
continue
for j in range(2*i, q+1, i):
candidates[j] = False
candidates[0] = candidates[1] = candidates[p] = False

nodes = [p]
step = 1
# 幅優先探索の開始
while len(nodes) > 0:
next = []
for x in nodes:
s = str(x)
# 始めの1文字除去
if len(s) > 1 and s[1] != ‘0’:
y = int(s[1:])
if candidates[y]:
next.append(y)
# 後ろの1文字除去
if len(s) > 1:
y = int(s[:len(s)-1])
if candidates[y]:
next.append(y)
# 始めに1文字追加
for c in range(1,10):
y = int(s + str(c))
if y

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

TOP