再帰処理を使って数値が素数かどうかを判定するPythonプログラム

再帰（リカーション）の手法を用いて、ある数値が素数かどうかを判定したい場合、判定用の関数を定義し、while 条件を組み合わせて処理を実装します。

再帰とは、大きな問題を小さな部分問題に分割してそれぞれの結果を計算し、それらを組み合わせることで全体の解を導き出す手法です。素数判定のように「同じ処理を条件が満たされるまで繰り返す」ケースに適しています。

そもそも素数とは、1とその数自身以外に正の約数を持たない、2以上の自然数のことです。たとえば 2、3、5、7、11 などが該当します。

サンプルコード

以下に実際の実装例を示します。

def check_prime(my_num, my_val = None):
    if my_val is None:
        my_val = my_num - 1
    while my_val >= 2:
        if my_num % my_val == 0:
            print("この数は素数ではありません")
            return False
        else:
            return check_prime(my_num, my_val-1)
    else:
        print("この数は素数です")
        return 'True'

my_num = int(input("判定したい数値を入力してください : "))
print("数値を確認中です…")
check_prime(my_num)

実行結果

判定したい数値を入力してください : 46
数値を確認中です…
この数は素数ではありません

処理の流れと解説

• まず check_prime という名前の関数を定義します。この関数は、判定対象の数値と、初期値として None が代入された変数をパラメータとして受け取ります。
• 変数が None の場合、その変数には「判定対象の数値から1を引いた値」が代入されます。これは自分自身で割り算を行わないようにするための工夫です。
• 変数の値が2以上である間、判定対象の数値をその変数の値で割り、余りが0になるかどうかを確認します。
• 余りが0であれば、約数が存在するということなので、その数は素数ではないと判断され、False が返されます。
• 余りが0でない場合は、数値と「1を減らした値」を引数として渡し、同じ関数を再帰的に呼び出します。これにより、割る数を1ずつ小さくしながら検証が繰り返されます。
• 割る数が2未満まで処理が進むと、それ以上約数は存在しないため、その数は素数であると判断されます。
• 関数の外側では、ユーザーに対して判定したい数値の入力を求めます。
• 入力された値を引数として関数を呼び出すことで判定が実行され、結果がコンソールに出力されます。

まとめ

このプログラムでは、再帰呼び出しによって割る数を段階的に減らしながら素数判定を行っています。ループ処理でも同様の判定は可能ですが、再帰を使うことで「残りの検証範囲」がひとつずつ縮んでいく様子がコード上で明確になり、再帰の仕組みを理解する良い練習例となります。なお、大きな数値を扱う場合は再帰の深さ制限に注意し、必要に応じて平方根までの範囲だけを調べるなどの最適化も検討するとよいでしょう。