初心者向けPython演習

Pythonで素数かどうかを判定する

このレッスンでは、平方根までの約数だけを調べて、ある数が素数かどうかを判定します。

  • 初級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

素数はインターネットの暗号化、ハッシュテーブル、多くのパズルの裏側にあります。その数自身までのすべての約数を試して素数か調べる方法は29なら使えますが、大きな数ではひどく遅くなります。ちょっとした気づきで、ずっと速く調べられます。

身近なたとえ

約数を調べるのは、タイルをすき間なく長方形に並べてみるのに似ています。36枚なら 1×36、2×18、3×12、4×9、6×6 に並べられます。正方形(6×6)を過ぎると、同じ長方形が向きを変えて出てくるだけなので、平方根より先を調べても新しいものは見つかりません。29枚は 1×29 にしか並べられないので、29 は素数です。

タイルの長方形からコードへ
number > 1🚪 素数になれるのは 1 より大きい数だけ
divisor * divisor <= number🪞 正方形で止める: その先の長方形はくり返し
number % divisor == 0🔍 すき間なく長方形になった: 素数ではない
divisor += 1➡️ 次の幅を試す
平方根まで約数が見つからなければ、その数は素数です。
ひと言でいうと

素数とは、1より大きい整数で、正の約数が1とその数自身だけのものです。

重要なポイント

  1. is_prime = number > 1 は、決して素数でない0、1、負の数に対して False から始めます。
  2. while divisor * divisor <= number and is_prime: は平方根に達するか、約数が見つかった時点で止まります。
  3. number % divisor == 0 は divisor がその数を割り切ることを意味します。
  4. 29の場合、ループは2、3、4、5を試すだけで素数だと分かります。

どんな場面で使う?

  • 素数の列挙や素因数分解などの数のパズル。
  • 早めに止めることや上限までだけ調べることで、ループが速くなる理由を学ぶ。
  • 数学ツールでの入力チェック。

使わなくてよいとき

  • 大きな上限までのすべての素数を列挙する場合:1つずつ調べるより、エラトステネスのふるいのほうがずっと速いです。
  • 何百桁もの数を扱う暗号:実際のシステムは確率的な判定法を使います。

サンプルコード

コードを実行 →
main.py
number = 29
is_prime = number > 1

divisor = 2
while divisor * divisor <= number and is_prime:
    if number % divisor == 0:
        is_prime = False
    divisor += 1

print(f"{number} is prime: {is_prime}")
この例の実行ボタンを作成

実行結果

29 is prime: True

コードの解説

ループはdivisor * divisor <= numberの間だけ約数を試せば十分です。nが平方根より大きい約数を持つなら、必ずそれと組になる小さい約数があり、そちらはループですでに調べているからです。これで計算量はO(√n)になり、結果から29が素数だとわかります。

値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。

発展問題

下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。

  1. 入力データを変え、実行する前に結果を予想してから確かめる。
  2. データが空のときや不正なときのチェックを追加する。
  3. 処理を別の関数にまとめ、いろいろなデータで試す。
Pythonコンパイラで実行 →

よくある間違い

1を素数として扱う

1の約数は1つだけなので素数ではありません。先に number > 1 を調べます。

問題
is_prime = True  # 1 would be reported as prime
修正
is_prime = number > 1

その数自身までループする

答えは正しくなりますが、必要よりはるかに多くの約数を試します。

問題
for divisor in range(2, number):
修正
while divisor * divisor <= number:

このレッスンを終えましたか?

学習済みにすると進み具合を記録できます。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ