Pythonで与えられた数値がユークリッド数（Euclid Number）かどうかを判定する方法

ユークリッド数とは？

ある整数 n が与えられたとき、それがユークリッド数であるかどうかを判定することを考えます。ユークリッド数とは、次の式で表すことができる整数のことです。

n = P_n + 1

ここで P_n は「最初の n 個の素数の積」を意味します。

例として、入力が n = 211 の場合を考えてみましょう。211 は次のように表せるため、出力は True になります。

211 = (2 × 3 × 5 × 7) + 1

解決のためのアプローチ

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

• 上限値 MAX を 10000 に設定し、空の素数リスト primes を用意します。
• 関数 generate_all_primes() を定義し、エラトステネスの篩を使って MAX 以下のすべての素数を生成します。
• メイン処理では、素数を先頭から順番に掛け合わせていき、「積 + 1」が n と一致するかどうかを確認します。

アルゴリズムの詳細

generate_all_primes() 関数では、まずサイズ MAX のブール型リスト prime をすべて True で初期化します。続いて x = 2 から始め、x² が MAX 未満である間、x が素数であれば x の倍数（x×2 以降、x 刻み）をすべて False にマークしていきます。最後に、True のまま残っているインデックスを素数リストへ追加します。

メインの solve() 関数では、mul を 1、i を 0 で初期化し、mul が n より小さい間、以下の処理を繰り返します。

• mul に primes[i] を掛ける
• mul + 1 が n と一致した場合は True を返す
• i を 1 増やす

ループが終了しても一致しなかった場合は False を返します。

サンプルコード

理解を深めるために、以下の実装例を見てみましょう。

MAX = 10000
primes = []

def generate_all_primes():
    prime = [True] * MAX

    x = 2
    while x * x < MAX :
        if prime[x] == True:
            for i in range(x * 2, MAX, x):
                prime[i] = False
        x += 1

    for x in range(2, MAX):
        if prime[x]:
            primes.append(x)

def solve(n):
    generate_all_primes()
    mul = 1
    i = 0

    while mul < n :
        mul = mul * primes[i]
        if mul + 1 == n:
            return True
        i += 1
    return False

n = 211
print(solve(n))

入力

211

出力

True

まとめ

このように、エラトステネスの篩であらかじめ素数を列挙しておき、素数の累積積を順に計算していくことで、与えられた数がユークリッド数かどうかを効率的に判定できます。計算量は素数生成部分が O(MAX log log MAX)、判定部分は n に到達するまでの積の計算のみなので、非常にシンプルで実用的な手法です。