Pythonで隣接する桁の絶対差の合計が素数かどうかを判定する方法

問題概要

ある整数 n が与えられたとき、隣り合う桁同士の絶対差の合計が素数であるかどうかを判定するプログラムを作成します。

例えば、入力が n = 574 の場合を考えてみましょう。

• |5 − 7| = 2
• |7 − 4| = 3
• 合計：2 + 3 = 5

5 は素数であるため、この場合の出力は True となります。

解法のアプローチ

この問題は以下の手順で解くことができます。

1. 整数 n を文字列に変換し、各桁に簡単にアクセスできるようにします。
2. 合計値を格納する変数 total を 0 で初期化します。
3. 文字列の先頭から順に、隣接する2つの桁の絶対差を計算して total に加算していきます。
4. 最終的な total が素数であれば True を、そうでなければ False を返します。

素数判定関数について

コード内の isPrime 関数は、2 から num - 1 までのすべての整数で割り切れるかどうかを順番に確認するシンプルな試し割り法を採用しています。num が 1 以下の場合は素数ではないため False を返します。より効率化したい場合は、√num まで確認すれば十分です。

実装コード

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

def solve(n):
    num_str = str(n)
    total = 0
    for i in range(1, len(num_str)):
        total += abs(int(num_str[i - 1]) - int(num_str[i]))

    if isPrime(total):
        return True
    return False

n = 574
print(solve(n))

入力

574

出力

True

処理の流れを詳しく見る

n = 574 の場合、プログラムは次のように動作します。

1. まず n を文字列 "574" に変換します。
2. i = 1 のとき：|int('5') − int('7')| = 2 を total に加算 → total = 2
3. i = 2 のとき：|int('7') − int('4')| = 3 を total に加算 → total = 5
4. isPrime(5) が True を返すため、最終的に True が出力されます。

計算量について

桁数を d とすると、絶対差の合計の計算には O(d) の時間がかかります。一方、素数判定は O(total) の時間が必要です。桁数が少ない通常の入力では非常に高速に動作しますが、より大きな数を扱う場合は素数判定を √total までの範囲に絞ることで効率を改善できます。