エラトステネスの篩(ふるい)で素数を求める

素数を求めるアルゴリズムの1つに**エラトステネスの篩(ふるい)**というものがあります。このアルゴリズムを使うと、2からNまでの範囲に存在する素数を効率的に求めることができます。

アルゴリズムの手順

エラトステネスの篩は以下の手順で実行します：

2からNまでの自然数を小さい順に並べます
最も小さい数をPとし（最初は2）、Pは素数として残しつつ、Pの倍数をすべて削除します
残った数の中からPの次に大きい数を新しいPとし、同様にPの倍数を削除します
Pが√Nより大きくなるまで、手順3を繰り返します
最終的に残った数が、求める範囲の素数となります

具体例として、2から30までの素数を求めてみましょう。

2から30までを並べます: {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30}
2の倍数を削除します: {2,3,5,7,9,11,13,15,17,19,21,23,25,27,29}
3の倍数を削除します: {2,3,5,7,11,13,17,19,23,25,29}
5の倍数を削除します: {2,3,5,7,11,13,17,19,23,29}
6は√30より大きいため、残った数字がすべて素数となります

TypeScriptでの実装

それでは、上記のアルゴリズムをTypeScriptで実装してみましょう。

/**
 * 各数値の状態を管理するインターフェース
 */
type NumberState = {
  flg: boolean;   // 素数かどうかのフラグ
  value: number;  // 実際の数値
}

/**
 * エラトステネスの篩を使って2からNまでの素数を求める
 * @param N - 上限値
 * @returns 素数の配列
 */
const findPrimeNumbers = (N: number): number[] => {
  // 2からNまでの数を管理する配列を作成
  const targets: NumberState[] = Array.from(
    { length: N + 1 },
    (_, i): NumberState => ({
      flg: true,
      value: i,
    })
  );

  // 0と1は素数ではないのでfalseにする
  targets[0].flg = false;
  targets[1].flg = false;

  // √Nまでの数でふるいをかける
  const max = Math.sqrt(N);
  for (let i = 2; i <= max; i++) {
    // すでにふるい落とされた数はスキップ
    if (!targets[i].flg) continue;

    // iの倍数をすべてふるい落とす
    for (let j = i * 2; j <= N; j += i) {
      targets[j].flg = false;
    }
  }

  // flgがtrueの数（素数）だけを取り出す
  const primeNumbers = targets.reduce<number[]>((acc, cur) => {
    if (cur.flg) {
      acc.push(cur.value);
    }
    return acc;
  }, []);

  return primeNumbers;
};

// 2から30までの素数を求める
const N = 30;
const primes = findPrimeNumbers(N);
console.log(primes); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

以上で、2から30までの素数を正しく求めることができました。

参考

エラトステネスの篩 - Wikipedia