#24

素数判定とエラトステネスの篩

素数判定と、範囲の素数をまとめて求める篩を学びます。

解説

素数は「1とその数自身でしか割り切れない2以上の整数」です。 まず1つの数の素数判定。2から順に割ってみて、1つでも割り切れたら素数ではありません。調べるのは平方根まで(i×i ≤ n)で十分です。 次に範囲の素数をまとめて求める「エラトステネスの篩」。 1. すべての数を素数候補とする。 2. 2の倍数、3の倍数…と素数の倍数を順に消す。 3. 最後まで残った数が素数。 割り算でなく「倍数を消す」発想で効率よく求められます。

書き方

素数判定: 2から i*i<=n まで割り、割り切れたら素数でない。
・エラトステネスの篩: sieve = [True]*(n+1) で候補管理。
・素数 i の倍数 range(i*i, n+1, i) を False に。
・[i for i in range(...) if sieve[i]] で残りを抽出(内包表記)。

書いて動かす

この回の課題

1つの数の素数判定 is_prime を作り、さらに篩で50以下の素数をまとめて求めて表示してみよう。

コードはあなたの端末の中だけで動きます(サーバーには送られません)。進み具合もこのブラウザに保存されます。

もっと本格的に使うなら

Windows版 InsightPy なら、書いたコードを保存して業務の自動化まで進められます。学習センターはずっと無料です。