0Pricing
Coding Interview Prep · レッスン

エラトステネスのふるい

N 以下のすべての素数をほぼ線形時間で列挙します

「エラトステネスのふるい」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

大量の素数を求める

1 つの数だけでなく、N 以下のすべての素数が必要になることがあります。エラトステネスのふるいなら、1 回の走査ですべて見つけられます。🧹

基本となる考え方

まず、すべての数が素数だと仮定します。次に、見つけた各素数の倍数を消していき、本当の素数だけを残します。

フラグを準備する

インデックス i が i が素数かどうかを表す boolean リストを作ります。この配列をキャンバスとして、ふるいを適用します。

is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False

候補を順に調べる

i を小さい方から順に調べます。まだ True のフラグが付いた数に初めて到達したなら、それは小さい因数を持たない新しい素数です。

倍数を消す

各素数 i について、2i、3i、4i などを素数でないと印付けします。これらの倍数は、明らかに i を約数として持つからです。

for j in range(i * i, n + 1, i):
    is_prime[j] = False

i の平方から始める

2i ではなく i*i から消し始めます。それより小さい倍数はすべて前の素数によってすでに消されているため、飛ばせます。

平方根で止める

ふるいを適用するのは、i*i が N 以下である間だけで十分です。平方根を超えた後に True のまま残っているフラグは、すでにすべて素数です。

ふるいの全体像

外側の走査と内側の消去処理を組み合わせます。ループの後、True のまま残っているすべてのインデックスが確認済みの素数です。

for i in range(2, int(n ** 0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, n + 1, i):
            is_prime[j] = False

素数を集める

内包表記を使って、完成したフラグをリストに読み込みます。これで、N 以下のすべての素数を高速な問い合わせに使える状態で保持できます。

primes = [i for i, p in enumerate(is_prime) if p]

高速な理由

ふるいの計算量はおよそ O(n log log n) で、ほぼ線形です。そのため、1 つずつ素数性を調べる方法を繰り返すより圧倒的に高速です。

メモリに注意する

フラグ配列が使うメモリは N に比例します。上限が非常に大きい場合は、確保する前に空間計算量の予算を確認してください。

確認

内側のループにある小さな最適化を思い出してください。

まとめ

これで、N 以下のすべての素数をほぼ線形時間で列挙するふるいを構築できるようになりました。各素数について i*i から始め、平方根で停止します。✅

よくある質問

「エラトステネスのふるい」レッスンは無料ですか？

はい。「エラトステネスのふるい」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「エラトステネスのふるい」で何を学びますか？

N 以下のすべての素数をほぼ線形時間で列挙します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「エラトステネスのふるい」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. GCD、LCM、ユークリッドの互除法
  2. sqrt(n) までの素数判定
  3. エラトステネスのふるい
  4. 素因数分解と約数
← Coding Interview Prepに戻る