JavaScript/Generator/素数ジェネレター

JavaScriptにおける「ジェネレータ関数」の力を活用して、素数を無限に生成する「エラトステネスの篩（Sieve of Eratosthenes）」を構築する方法をご紹介します。ジェネレータは、遅延評価とステートフルなイテレーションを実現する非常に強力な構文です。この記事ではその応用として、無限の整数ストリームから素数だけを抽出する実用的かつエレガントなパターンを示します。

// 2, 3, 4, ...という無限の数列を生成するジェネレータ関数
function* generate() {
  for (let i = 2;; i++) {
    yield i;
  }
}

// フィルタジェネレータ関数
// 'in'ジェネレータから値を受け取り、'prime'で割り切れない値を返す
function* filter(inputGenerator, prime) {
  for (const i of inputGenerator) {
    if (i % prime !== 0) {
      yield i;
    }
  }
}

// 素数篩 (Sieve) のジェネレータ関数
// 素数を生成する
function* sieve() {
  let inputGenerator = generate(); // 最初の入力は無限数列のジェネレータ
  for (;;) {
    const prime = inputGenerator.next().value; // 次の素数を取得
    yield prime; // 素数を出力
    // 取得した素数でフィルタリングする新しいジェネレータを作成
    inputGenerator = filter(inputGenerator, prime);
  }
}

// 素数を100まで出力
function main() {

  for (const prime of sieve()) {
    if (prime > 100) {
      break;
    }
    console.log(prime);
  }
}

main();

ステップ1：無限数列のジェネレータ

まず、2 から始まる無限の整数列を生成するジェネレータ generate を用意します。

function* generate() {
  for (let i = 2;; i++) {
    yield i;
  }
}

これは、for ループが無限に続くことで、任意のタイミングで .next() を呼べば次の整数が取得できます。

ステップ2：フィルタ関数による除外

次に、ある素数 prime で割り切れない整数だけを通す フィルタジェネレータを定義します：

function* filter(inputGenerator, prime) {
  for (const i of inputGenerator) {
    if (i % prime !== 0) {
      yield i;
    }
  }
}

この関数は、入力となる整数ストリーム inputGenerator を監視し、prime の倍数を除外して次のジェネレータへバトンタッチします。

ステップ3：エラトステネスの篩をジェネレータで表現

この filter を段階的に組み合わせて素数だけを取り出す「篩」の役割を果たすジェネレータがこちらです：

function* sieve() {
  let inputGenerator = generate(); // 無限の整数列

  for (;;) {
    const prime = inputGenerator.next().value; // 次の素数を取得
    yield prime; // 見つかった素数を出力
    // 素数の倍数を除いた新しいジェネレータを構築
    inputGenerator = filter(inputGenerator, prime);
  }
}

この sieve 関数では、見つかった素数でフィルタリングを繰り返しながら、常に次の素数を抽出します。この構造そのものが「篩（Sieve）」の概念を忠実に再現していると言えるでしょう。

ステップ4：素数を出力する `main` 関数

最後に、100 以下の素数を出力する実行関数です：

function main() {
  for (const prime of sieve()) {
    if (prime > 100) {
      break;
    }
    console.log(prime);
  }
}
main();

この main 関数は、sieve() から素数を順に受け取り、100 を超えるまで出力します。

出力例

このコードの特徴と利点

✅ 無限ストリームを効率的に処理できる
✅ 状態を持つ関数の再帰的な構成が可能（関数型プログラミング的アプローチ）
✅ 必要な数だけ素数を取り出す遅延評価により無駄がない
✅ 低メモリ・高効率なフィルタリング

応用例と発展

このアプローチは、以下のような用途にも応用できます：

任意の条件によるストリームのフィルタリング
イベントストリーム処理やリアクティブプログラミング
無限系列の中から特定パターンを抽出する解析ツール

まとめ

JavaScriptのジェネレータは、単なる繰り返し構文を超えて、「流れ」を制御する表現力豊かな手段です。エラトステネスの篩という古典的なアルゴリズムと、現代的なジェネレータを組み合わせることで、簡潔かつ効率的な素数生成が実現できます。