CodeIQ MAGAZINECodeIQ MAGAZINE

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

2016.08.09 Category:CodeIQ問題解説・リーダーボード Tag: ,

  • 10
  • このエントリーをはてなブックマークに追加
riverplus

「数学の問題をプログラミングで解こう!」シリーズ。
今回はいつもと違って、数学というよりもアルゴリズムの問題に近い内容でした。
素数をグラフのノードとみなして考えましょう。

みなさんはうまくできましたか?
ぜひ出題者のKawazoeさんによる本記事で解法をチェックして下さい!
by CodeIQ運営事務局

問題のおさらい

ある素数に対し、次の変換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 のつく数への変換はできません。

さて、素数 pqpq)が与えられたときに、素数 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, qpq かつ 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 <= q and candidates[y]:
                next.append(y)
        # 後ろに1文字追加
        for c in range(1,10):
            y = int(str(c) + s)
            if y <= q and candidates[y]:
                next.append(y)
    # リストの更新
    nodes = []
    for y in next:
        if y == q:
            # 目的の素数を発見!
            print step
            exit()
        if candidates[y] == True:
            candidates[y] = False
            nodes.append(y)
    step += 1
print -1

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)こちらもぜひチェックして下さい。

CodeIQ「プライム・ホッパー」 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
現在、Kawazoeさんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

  • 10
  • このエントリーをはてなブックマークに追加

■関連記事

数学の問題をプログラミングで解こう!「ロンリー・ルーク」問題解説... 問題のおさらい 自然数 n, k に対し、縦横 n×n のマス目にチェスのルークの駒を k 個配置することを考えます。 このとき、自身から見て上下方向・左右方向のいずれにも他の駒が存在しないような駒を「はぐれルーク」と呼びます。 例えば以下は、(n, k)=(4, 5) のときの駒の配置例を示...
【謎解きプログラム】どんな数字になる?【整数のキャスト】... 【謎解きプログラム】どんな数字になる?【整数のキャスト】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24...
【謎解きプログラム】テキストのバイナリは?【テキスト バイナリ】解答と解説... 【謎解きプログラム】テキストのバイナリは?【テキスト バイナリ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 ...
【謎解きプログラム】条件に当てはまる文字列は?【正規表現】解答と解説... 【謎解きプログラム】条件に当てはまる文字列は?【正規表現】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「2...
数学の問題をプログラミングで解こう!「クロッシング・ワード」問題解説... 問題のおさらい クロスワードの盤面では、格子状のマス目に白マスまたは黒マスを配置します。 以下は、縦 3 個×横 4 個のマス目に白マス・黒マスを配置する例です。 白マス・黒マスの配置には次のルールがあります。 黒マスによって白マスの領域が分断されてはならない。 黒マスが縦・横に連続し...
【謎解きプログラム】乱数で発生する数値は?【組み合わせ】解答と解説... 【謎解きプログラム】乱数で発生する数値は?【組み合わせ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ