n 以下の素数を列挙する｜コードで実践

n 以下の素数を列挙するとは

ネストループと条件判定の組み合わせで、n 以下の素数をすべて配列で返す関数を書こう。本レッスンでは、n 以下の素数を列挙するの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

素数列挙でネストループを実戦練習する

ここまでのレッスンで for while for-of for-in break continue ネストループを学んできました。今回はこれらの知識を組み合わせた応用問題、素数の列挙 に挑戦します。古代ギリシャの数学者ユークリッドの時代から研究されてきた、コンピュータサイエンスの定番テーマです。

素数とは「1 と自分自身でしか割り切れない 2 以上の自然数」です。2, 3, 5, 7, 11, 13, 17, 19, 23 ... と続きます。1 は素数ではない、2 は唯一の偶数の素数、というポイントは覚えておきましょう。プログラミング教材では「ループの良い練習材料」として頻出します。

素朴な判定アルゴリズム

ある数 n が素数かどうかを判定する最も素朴な方法は、「2 から n - 1 まで順番に割っていく」です。1 つでも割り切れる数があれば素数ではない、すべて割り切れなければ素数、という判定になります。

JavaScript

function isPrime(n) {
  if (n < 2) {
    return false;
  }
  for (let i = 2; i < n; i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

この関数を 2 から n まで全部の数に適用すれば、素数のリストが手に入ります。

JavaScript

function listPrimes(n) {
  const primes = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime(i)) {
      primes.push(i);
    }
  }
  return primes;
}

これが基本形です。外側のループ で「素数候補」を 1 つずつ取り、内側のループ で「その候補が本当に素数か」を判定する、典型的なネストループです。

平方根で打ち切る最適化

素朴な実装には無駄があります。n が 36 のとき、i = 2 から i = 35 まで全部割らなくても、i = 6 まで調べれば十分なのです。理由は、36 = 6 x 6 のように、約数は 平方根を境にしてペア で現れるからです。36 = 2 x 18 = 3 x 12 = 4 x 9 = 6 x 6 で、6 を超えると 18, 12, 9 などのペアの片割れしか出てきません。

この性質を使えば、内側のループは i * i <= n まで回せば十分です。

JavaScript

function isPrimeFast(n) {
  if (n < 2) {
    return false;
  }
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

n = 100 だと、素朴版は最大 99 回ループしますが、最適化版だと 10 回までで済みます。n = 10000 なら 100 回、n = 1000000 なら 1000 回、と圧倒的に高速化します。アルゴリズムの工夫がパフォーマンスに直結する、典型的な例です。

計算量の表現で言うと、素朴版は O(n)、平方根打ち切り版は O(sqrt(n)) になります。O(sqrt(n)) は O(n) よりずっと速く、n が大きくなるほど差が広がります。一般に O(log n) < O(sqrt(n)) < O(n) < O(n log n) < O(n^2) < O(2^n) という階段があり、この感覚を身につけるのがアルゴリズムを学ぶ第一歩です。

break で内側を抜ける

上記の実装では return false; を使って関数全体を抜けていますが、関数化していない場合は break を使うことになります。

JavaScript

function listPrimesFlat(n) {
  const primes = [];
  for (let num = 2; num <= n; num++) {
    let isPrime = true;
    for (let i = 2; i * i <= num; i++) {
      if (num % i === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) {
      primes.push(num);
    }
  }
  return primes;
}

外側のループ (num) で素数候補を回し、内側のループ (i) で「割り切れる数があるか」を探します。見つかった瞬間に isPrime = false; break; で内側のループを抜けて、外側に戻ります。

このスタイルは「isPrime フラグを使ったネストループの典型パターン」として覚えておくと、他のアルゴリズムにも応用できます。

実行フローを図で追ってみる

素数列挙の流れは次のとおりです。

diagram (will load when visible)

やや複雑ですが、これまでに学んだ要素「ネストループ + フラグ変数 + break + 条件分岐」が全部入っています。ループ系の総決算とも言える図です。

よくある間違い

素数列挙でハマりやすい落とし穴が 3 つあります。

1 を素数として返してしまう — 数学の定義で 1 は素数ではありません。if (n < 2) return false; のような早期 return を入れて除外する必要があります
i < n の範囲を間違える — 内側のループを i <= n にすると n % n === 0 で必ず割り切れて全て非素数扱いになります。i < n または i * i <= n が正解です
平方根の計算で誤差が出る — Math.sqrt(n) を使うときは浮動小数点誤差で Math.sqrt(25) が 4.9999... になることがあります。整数比較なら i * i <= n のほうが安全です

エラトステネスのふるい という、もっと高速な素数列挙アルゴリズムもあります。配列を使って「素数の倍数を順番に消していく」やり方で、O(n log log n) の効率があります。今回は素朴版で十分ですが、興味があれば「エラトステネス」で検索してみてください。古代ギリシャの図書館長の名前がアルゴリズム名になっているのは少し格好いいです。

もうひとつ、素数判定は 暗号 (RSA など) の基礎にも使われています。Web の HTTPS 通信や、Bitcoin などの暗号通貨も、巨大な素数の性質を利用したアルゴリズムで動いています。一見地味な素数列挙が、現代インターネットの裏側を支えている、と思うと少しテンションが上がりますね。

やってみよう

それでは今回の課題に取り組みましょう。やることは次の通りです。

listPrimes(n) 関数の中身を埋める
n 以下の全ての素数を昇順に並べた配列を返す
listPrimes(10) は [2, 3, 5, 7]、listPrimes(20) は [2, 3, 5, 7, 11, 13, 17, 19]、listPrimes(1) は [] を返す

ヒントとして、外側のループで num を 2 から n まで回し、内側のループで i を 2 から i * i <= num まで回して割り切れるか調べます。isPrime フラグを使ってネストループを管理しましょう。

余裕があれば、平方根打ち切り版 (i * i <= num) と素朴版 (i < num) でどれだけ速さに差が出るか、console.time で測ってみてください。アルゴリズムの違いが体感できると、効率を意識する習慣が身に付きます。

これで第 5 章「ループ」の coding パートは終了です。次のレッスンは章末クイズで、ここまで学んだループの知識を腕試しします。お疲れさまでした。

よくある質問

Q. ブラウザと Node.js で動作は変わりますか？

A. JavaScript の構文・組み込み機能（配列・文字列・Promise 等）はどちらでも同じです。違いは DOM API（ブラウザ専用）と fs などのファイル系（Node 専用）など、実行環境固有の機能です。コアロジックは両方で動くため、テストもしやすくなります。

Q. ES6 以降の新機能は使っても大丈夫ですか？

A. 現代のブラウザ・Node.js は ES2020 以降の機能をほぼサポートしています。古い IE 等を対象にする必要が無ければ、let/const、アロー関数、分割代入、async/await を積極的に使ってください。トランスパイル（Babel/Vite）が必要なケースは年々減っています。

Q. TypeScript に進む価値はありますか？

A. 型情報があるとリファクタやエディタ補完が劇的に効くため、規模が大きくなるなら TypeScript への移行を強くおすすめします。最初は any を許容しつつ徐々に型を付ければ、JS の知識をそのまま活かせます。

次のレッスン

次は 第 5 章まとめクイズ で、ネストループと条件判定の組み合わせで、n 以下の素数をすべて配列で返す関数を書こうを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

素数列挙の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 素数列挙とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

n 以下の素数を列挙する

素数列挙でネストループを実戦練習する

素朴な判定アルゴリズム

平方根で打ち切る最適化

break で内側を抜ける

実行フローを図で追ってみる

よくある間違い

やってみよう

よくある質問

Q. ブラウザと Node.js で動作は変わりますか？

Q. ES6 以降の新機能は使っても大丈夫ですか？

Q. TypeScript に進む価値はありますか？

次のレッスン

要件

入出力例

ヒント

メモ