はじめに
どんな問題を解決するか
素数はインターネットの暗号化、ハッシュテーブル、多くのパズルの裏側にあります。その数自身までのすべての約数を試して素数か調べる方法は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とその数自身だけのものです。
重要なポイント
is_prime = number > 1は、決して素数でない0、1、負の数に対して False から始めます。while divisor * divisor <= number and is_prime:は平方根に達するか、約数が見つかった時点で止まります。number % divisor == 0はdivisorがその数を割り切ることを意味します。- 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を素数として扱う
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 のレビューも受けられます。
- 素数判定 数が素数かどうかを判定してください。 簡単
- 最大の素因数 正の整数を割り切る最大の素数を求めてください。 中級
- List Primes With a Sieve Find primes up to a limit by marking composite multiples. 中級