CodeIQ MAGAZINECodeIQ MAGAZINE

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

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

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

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

みなさんはうまくできましたか?
ぜひ出題者の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
  • このエントリーをはてなブックマークに追加

■関連記事

【謎解きプログラム】この処理は?【コードを読もう】解答と解説... 【謎解きプログラム】この処理は?【コードを読もう】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以...
数学の問題をプログラミングで解こう!「ループ・トラッキング」問題解説... 問題のおさらい 自然数 n に対し、関数 Fn(x) を次のように定義します(floor():床関数)。 例えば n=10, x=1 のとき、F10(1) = floor(4×1×9÷10) = 3 です。 さて、整数 k(0 ≦ k ≦ n)に対して、関数 Fn による変換を繰り返し行い...
【謎解きプログラム】どんな結果になる?【アロー関数】解答と解説... 【謎解きプログラム】どんな結果になる?【アロー関数】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...
数学の問題をプログラミングで解こう!「カウント・スリー」問題解説... 問題のおさらい 自然数を 1 から順に書き並べていきます。 このとき、3 の数字が現れる回数を数えます。 自然数 n に対し、ちょうど n 個目の 3 の数字が現れたときに書いている数を F(n) と定義します。 例えば F(10)=35 です。 下の通り、10 個目の 3 は、35 を書いて...
【息抜き】カードを上手く並べよう【言語不問】解答と解説... 【息抜き】カードを上手く並べよう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 あなたは、11から99までの、89枚のカードを持っています。問題では、横幅と高さの整数が与えられます。この横幅と高さで作られるマス...
【コードミステリ】数字に隠されたメッセージ【言語不問】解答と解説... 【コードミステリ】数字に隠されたメッセージ【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 喜屋武ちあきさんによるCodeIQ MAGAZINEでのブックレビューに合わせて、『顔貌売人』(文藝春秋)とのコラボ問題として出題されたものです。 それでは以下、問題とその解...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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