JavaScriptでn未満のすべての素数の合計を求める方法

この記事では、数値を1つだけ引数として受け取り、その数より小さいすべての素数の合計を計算して返すJavaScript関数を作成します。

たとえば n = 10 の場合、10未満の素数は 2・3・5・7 の4つなので、関数はそれらの合計である 17 を返す必要があります。

素数判定の考え方

ある数が素数かどうかを判定する最も単純な方法は、2からその数自身まで順番に割り切れるかを確認することですが、これは非効率です。平方根まで試し割りをするだけで十分であり、計算量を大きく削減できます。

理由は、num = a × b と表せる場合、a と b の少なくとも一方は必ず √num 以下になるためです。したがって、√num 以下のどの数でも割り切れないなら、その数は素数であると判断できます。

コード例

const isPrime = (num) => {
   let x = Math.floor(Math.sqrt(num));
   let j = x;
   while (j >= 2) {
      if (num % j === 0) {
         return false;
      }
      j--;
   }
   return true;
};
const sumOfPrimes = (num = 10) => {
   let iter = num;
   let sum = 0;
   while (iter >= 2) {
      if (isPrime(iter) === true) {
         sum += iter;
      }
      iter--;
   }
   return sum;
};
console.log(sumOfPrimes(14));
console.log(sumOfPrimes(10));

出力結果

コンソールには次のように出力されます。

41
17

sumOfPrimes(14) は 2 + 3 + 5 + 7 + 11 + 13 = 41、sumOfPrimes(10) は 2 + 3 + 5 + 7 = 17 となるためです。

コードの解説

isPrime関数（素数判定）

Math.floor(Math.sqrt(num)) で num の平方根の整数部分を取得し、そこから2に向かって降順に割り切れるかどうかを調べます。1つでも割り切れる数が見つかれば合成数なので false を返し、最後まで見つからなければ true（素数）を返します。

sumOfPrimes関数（合計の算出）

引数で受け取った数値から2まで降順にループ処理を行い、isPrime関数によって素数と判定された数だけを変数 sum に加算していきます。デフォルト引数として 10 が設定されているため、引数なしで呼び出した場合は10未満の素数の合計が返されます。

さらに高速な手法：エラトステネスの篩

n が非常に大きい場合（例：100万以上など）、1つずつ素数判定を繰り返す方式では処理時間が長くなります。そのようなケースではエラトステネスの篩（ふるい）を利用すると、O(n log log n) という高い効率で素数を一括して抽出でき、合計も格段に速く求められます。