【Python】桁の配列から最小の数を作り、先頭と末尾の桁でできる数が素数かどうか判定する方法

問題の概要

0〜9の数字だけを要素に持つ配列 digits が与えられます。まず、これらの桁をすべて使って作れる最小の数を求めます。次に、その数の先頭の桁と末尾の桁を組み合わせてできる2桁の数(順方向・逆方向の2通り)が素数かどうかを判定し、生成した数と素数の結果を出力します。

たとえば、入力が digits = [5, 2, 1, 7] の場合を考えてみましょう。桁を昇順に並べると最小の数は 1257 になります。先頭と末尾の桁は「1」と「7」なので、組み合わせは 17 と 71 の2つ。この2つはどちらも素数であるため、プログラムは 1257、17、71 を返します。

解法のアプローチ

最小の数を作る基本は、各桁の出現回数を数えたうえで小さい桁から順に並べることです。全体の流れは以下のとおりです。

1. 出現頻度の集計： 各数字(0〜9)が何回現れるかを辞書(マップ)に記録します。
2. 最小数の構築： 0から9までの順に、記録された回数だけ桁を文字列へ連結していきます。
3. 2桁の数の生成： 完成した数の先頭と末尾の桁を取り出し、「先頭＋末尾」「末尾＋先頭」の2通りの整数を作ります。
4. 素数判定： それぞれの数について素数かどうかを調べ、結果に応じて値を返します。

素数判定について

素数判定にはシンプルな試し割り法を使用します。2から num−1 までの整数で順に割り、1つでも割り切れる数があれば素数ではないと判断します。今回は2桁の数しか判定しないため、この方法で十分高速です。

Pythonでの実装例

from collections import defaultdict

def isPrime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def solve(arr):
    # 各桁の出現回数を集計
    digits_freq = defaultdict(int)
    for i in range(len(arr)):
        digits_freq[arr[i]] += 1

    # 小さい桁から順に連結して最小の数を作る
    number = ""
    for i in range(0, 10):
        for j in range(digits_freq[i]):
            number += str(i)

    # 先頭＋末尾 / 末尾＋先頭 の2つの数を生成
    num = int(number[0] + number[-1])
    rev = int(number[-1] + number[0])

    if isPrime(num) and isPrime(rev):
        return int(number), num, rev
    elif isPrime(num):
        return number, num
    elif isPrime(rev):
        return number, rev
    else:
        return False

digits = [5, 2, 1, 7]
print(solve(digits))

入力

[5, 2, 1, 7]

出力

(1257, 17, 71)

コードのポイント

• defaultdict(int): 存在しないキーにアクセスすると自動的に 0 で初期化されるため、出現回数のカウントを簡潔に書けます。
• number[0] と number[-1]: Pythonの文字列インデックスを活用すれば、先頭の桁と末尾の桁を簡単に取得できます。
• 戻り値の分岐： 両方が素数なら3つの値、片方だけが素数なら2つの値、どちらも素数でなければ False を返します。

計算量について

桁の並べ替え部分は各桁を一度ずつ処理するため O(n)(n は桁の個数)、素数判定は試し割り法により最大 O(k)(k は判定対象の数)です。本記事のように2桁の数しか判定しない場合、実用上はきわめて高速に動作します。