解説
素数は「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 なら、書いたコードを保存して業務の自動化まで進められます。学習センターはずっと無料です。