JavaScriptで学ぶ！与えられた数以下の素数の合計を効率的に計算するアルゴリズム💻

はじめに (対象読者・この記事でわかること)

この記事は、JavaScriptの学習を進めている方、アルゴリズムに興味がある方、または効率的なプログラミング手法について学びたい方を対象としています。特に、プログラミングコンテストや面接でよく出題されるアルゴリズム問題の一つである「素数の合計」について、その解法と最適化を理解したい方に最適です。

この記事を読むことで、以下のことがわかる・できるようになります。

• 素数とは何か、そして素数に関連するアルゴリズム問題の基本的な考え方。
• 素数判定のナイーブな方法とそのパフォーマンス上の課題。
• 「エラトステネスのふるい」という効率的な素数探索アルゴリズムの原理と実装方法。
• JavaScriptを使って、指定された数以下のすべての素数の合計を効率的に計算する方法。
• 計算効率（パフォーマンス）の重要性と、アルゴリズムがコードの実行速度に与える影響。

日常的な開発では直接素数計算を行う機会は少ないかもしれませんが、本記事を通して学べるアルゴリズム的思考やパフォーマンス最適化の考え方は、どのようなプログラミング課題にも応用できる汎用的なスキルです。ぜひ最後まで読んで、アルゴリズムの世界に触れてみてください。

前提知識

この記事を読み進める上で、以下の知識があるとスムーズです。 * JavaScriptの基本的な構文（変数、条件分岐、ループ、関数など） * 配列の基本的な操作

素数計算の基礎：問題の理解と効率化の必要性

素数とは何か？

まず、素数とは何かを明確にしておきましょう。素数とは、1とその数自身以外に正の約数を持たない自然数で、1より大きい整数を指します。例えば、2, 3, 5, 7, 11などが素数です。1は素数ではありません。

今回の問題は、「与えられた引数 n 以下のすべての素数の合計を返す」というものです。例えば、n = 10 の場合、10以下の素数は 2, 3, 5, 7 ですので、その合計は 2 + 3 + 5 + 7 = 17 となります。

なぜ効率的なアルゴリズムが必要なのか？

一見すると単純な問題に見えるかもしれませんが、n が非常に大きな値（例えば100万や1000万）になった場合、素朴な方法では計算に膨大な時間がかかってしまいます。このようなケースでは、プログラムの実行速度が著しく低下し、最悪の場合はタイムアウトしたり、コンピューターが応答しなくなることもあります。

そこで重要になるのが「効率的なアルゴリズム」です。同じ問題を解決するにも、アルゴリズムの選び方一つで、計算にかかる時間が劇的に変わることがあります。今回の素数合計の問題は、まさにその効率化の重要性を学ぶのに最適な題材と言えるでしょう。

ナイーブなアプローチの課題

最も素朴な方法を考えてみましょう。 1. 2から n までのそれぞれの数について、それが素数であるかどうかを判定する。 2. 素数であれば合計に加算する。

このアプローチでは、各数に対して素数判定を行う必要があります。素数判定自体も、与えられた数が素数かどうかを調べるために、その数を2からその数の平方根までで割ってみる（Math.sqrt(num)）というループ処理が必要になります。

例えば、100万以下の素数をすべて探そうとすると、100万回近くの素数判定が必要になり、それぞれの判定もsqrt(N)回の割り算を伴います。これは N * sqrt(N) に近い計算量となり、非常に非効率です。

このような背景から、私たちはより高速な素数探索アルゴリズム「エラトステネスのふるい」の力を借りる必要が出てくるのです。

JavaScriptで実装する効率的な素数合計アルゴリズム

ここでは、まずナイーブな素数判定を試してから、より効率的な「エラトステネスのふるい」を導入し、最終的に素数の合計を計算する関数を実装していきます。

ステップ1: ナイーブな素数判定関数を考える

まずは、ある数が素数であるかを判定する最も基本的な関数をJavaScriptで実装してみましょう。これは、後で効率性の違いを比較する際の基準にもなります。

Javascript

/**
 * 与えられた数が素数であるかを判定する（ナイーブな方法）
 * @param {number} num 判定する数
 * @returns {boolean} 素数であればtrue、そうでなければfalse
 */
function isPrimeNaive(num) {
    // 1以下は素数ではない
    if (num <= 1) return false;
    // 2は唯一の偶数の素数
    if (num === 2) return true;
    // 偶数は2以外素数ではない
    if (num % 2 === 0) return false;

    // 3からnumの平方根まで奇数のみを試す
    // ループ回数を減らすために、約数は平方根を超えないという性質を利用
    for (let i = 3; i * i <= num; i += 2) {
        if (num % i === 0) {
            return false; // 割り切れたら素数ではない
        }
    }
    return true; // 割り切れなければ素数
}

// テスト
console.log("isPrimeNaive(7):", isPrimeNaive(7));   // true
console.log("isPrimeNaive(10):", isPrimeNaive(10)); // false
console.log("isPrimeNaive(29):", isPrimeNaive(29)); // true

/**
 * ナイーブな方法で、指定された数以下の素数の合計を計算する
 * @param {number} limit 上限値
 * @returns {number} 素数の合計
 */
function sumOfPrimesNaive(limit) {
    let sum = 0;
    for (let i = 2; i <= limit; i++) {
        if (isPrimeNaive(i)) {
            sum += i;
        }
    }
    return sum;
}

console.time("sumOfPrimesNaive(10000)");
console.log("10000までの素数の合計 (ナイーブ):", sumOfPrimesNaive(10000)); // 少し時間がかかる
console.timeEnd("sumOfPrimesNaive(10000)");

// もし `limit` を100,000や1,000,000にすると、著しく遅くなることが体感できるはずです。
// console.time("sumOfPrimesNaive(100000)");
// console.log("100000までの素数の合計 (ナイーブ):", sumOfPrimesNaive(100000));
// console.timeEnd("sumOfPrimesNaive(100000)");

このナイーブな方法では、limit が大きくなるにつれて計算時間が爆発的に増大します。特に100,000や1,000,000のような値では、現実的な時間で計算を終えることが困難になります。

ステップ2: 素数判定の効率化：エラトステネスのふるい

ここで、古代ギリシャの数学者エラトステネスが考案した「エラトステネスのふるい (Sieve of Eratosthenes)」というアルゴリズムを導入します。これは、ある数までのすべての素数を効率的に見つけるための非常に優れた方法です。

エラトステネスのふるいの原理

1. 2から n までの整数をすべてリストアップします。
2. 最初に残っている最小の数（2）は素数です。その数を素数としてマークし、その倍数（4, 6, 8, ...）をリストから除外します。
3. 次に残っている最小の数（3）は素数です。その数を素数としてマークし、その倍数（6, 9, 12, ...）をリストから除外します。
4. これを、現在注目している数の平方根が n を超えるまで繰り返します。
5. リストに残った数がすべて素数です。

このアルゴリズムの素晴らしい点は、一度計算すると、その範囲内のすべての素数をまとめて見つけられることです。個別の数について何度も素数判定を行うナイーブな方法に比べて、はるかに効率的です。

JavaScriptでの実装

エラトステネスのふるいを実装するために、ブール値の配列（true が素数の候補、false が素数ではない）を使用します。

Javascript

/**
 * エラトステネスのふるいを用いて、指定された数以下の素数をすべて見つける
 * @param {number} limit 上限値
 * @returns {boolean[]} limitまでの各インデックスが素数かどうかを示すブール配列
 */
function sieveOfEratosthenes(limit) {
    // limit + 1 のサイズのブール配列を作成し、すべてtrueで初期化
    // isPrime[i] は i が素数であるかどうかを示す
    const isPrime = new Array(limit + 1).fill(true);

    // 0と1は素数ではない
    isPrime[0] = false;
    isPrime[1] = false;

    // 2から平方根までを繰り返す
    // i * i <= limit は i <= Math.sqrt(limit) と同じ意味
    for (let p = 2; p * p <= limit; p++) {
        // もし p がまだ素数としてマークされている場合
        if (isPrime[p]) {
            // p の倍数 (p*p から) をすべて素数ではないとマークする
            // p * p より小さい p の倍数は、p より小さい素数によって既にマークされているため
            for (let multiple = p * p; multiple <= limit; multiple += p) {
                isPrime[multiple] = false;
            }
        }
    }

    return isPrime;
}

// テスト
const primesUpTo10 = sieveOfEratosthenes(10);
console.log("10までの素数候補 (trueが素数):", primesUpTo10);
// [false, false, true, true, false, true, false, true, false, false, false]
// (インデックスが数に対応: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

この sieveOfEratosthenes 関数は、limit までの素数かどうかを示すブール配列を返します。次に、この配列を使って素数の合計を計算します。

ステップ3: エラトステネスのふるいを用いた素数の合計計算

sieveOfEratosthenes 関数で得られたブール配列を利用して、素数の合計を計算する関数を作成します。

Javascript

/**
 * エラトステネスのふるいを用いて、指定された数以下の素数の合計を計算する
 * @param {number} limit 上限値
 * @returns {number} 素数の合計
 */
function sumOfPrimesSieve(limit) {
    if (limit < 2) return 0; // 2未満には素数がない

    const isPrime = sieveOfEratosthenes(limit); // ふるいを実行

    let sum = 0;
    for (let i = 2; i <= limit; i++) {
        if (isPrime[i]) {
            sum += i; // 素数であれば合計に加算
        }
    }
    return sum;
}

// テスト
console.log("10までの素数の合計 (ふるい):", sumOfPrimesSieve(10)); // 17

// パフォーマンス比較
console.time("sumOfPrimesSieve(100000)");
console.log("100000までの素数の合計 (ふるい):", sumOfPrimesSieve(100000));
console.timeEnd("sumOfPrimesSieve(100000)");

console.time("sumOfPrimesSieve(1000000)");
console.log("1000000までの素数の合計 (ふるい):", sumOfPrimesSieve(1000000));
console.timeEnd("sumOfPrimesSieve(1000000)");

console.time("sumOfPrimesSieve(10000000)");
console.log("10000000までの素数の合計 (ふるい):", sumOfPrimesSieve(10000000));
console.timeEnd("sumOfPrimesSieve(10000000)");

この sumOfPrimesSieve 関数を実行すると、100,000 や 1,000,000、さらには 10,000,000 といった大きな数に対しても、ナイーブな方法とは比較にならないほど高速に計算が完了することがわかるでしょう。

エラトステネスのふるいの計算量は、およそ O(N log log N) と非常に効率的です。これは、N * sqrt(N) のナイーブな方法と比較して、特に N が大きい場合に圧倒的な差を生み出します。

パフォーマンスの壁とエラトステネスのふるいの威力

ナイーブな sumOfPrimesNaive 関数と、エラトステネスのふるいを使った sumOfPrimesSieve 関数を比較してみましょう。

例えば、limit = 100,000 の場合: - sumOfPrimesNaive(100000): 数秒〜数十秒かかる可能性があります。（環境による） - sumOfPrimesSieve(100000): 数ミリ秒〜数十ミリ秒で完了します。

limit が 1,000,000 になると、ナイーブな方法では数分、あるいはそれ以上かかることも珍しくありませんが、エラトステネスのふるいではわずか数十ミリ秒から数百ミリ秒で結果が出ます。

このパフォーマンスの差は、アルゴリズムの選び方一つでプログラムの実行効率がいかに変わるかを示す典型的な例です。特に、繰り返し実行される処理や、大量のデータを扱う場面では、アルゴリズムの最適化が非常に重要になります。

解決策

エラトステネスのふるいは、素数の合計を計算する上で非常に効果的な解決策です。その鍵は以下の点にあります。

1. 重複計算の回避: ナイーブな方法が各数に対して素数判定を繰り返すのに対し、ふるいは一度素数が見つかれば、その倍数は二度とチェックする必要がありません。これにより、大幅に計算量を削減します。
2. 空間計算量とのトレードオフ: ブール配列を limit + 1 のサイズで作成するため、メモリを消費しますが、これは時間計算量の劇的な改善と引き換えになります。通常、現代のコンピュータではこの程度のメモリ使用は問題になりません。

このようなアルゴリズムを理解し、適切に使いこなすことで、より効率的で高性能なプログラムを開発できるようになります。

まとめ

本記事では、JavaScriptで与えられた数以下のすべての素数の合計を計算するアルゴリズムについて解説しました。

• 素数の定義と問題設定：素数とは何かを理解し、素数の合計を求める問題の基本的な考え方を把握しました。
• ナイーブなアプローチの課題：一つ一つ素数判定を行う素朴な方法では、大きな数に対しては計算時間が膨大になり、パフォーマンス上の問題があることを確認しました。
• エラトステネスのふるいの導入：古代から伝わる効率的な素数探索アルゴリズム「エラトステネスのふるい」の原理を学び、その実装方法をJavaScriptで具体的に示しました。このアルゴリズムは、重複計算を避け、素早く素数を特定できます。
• 効率的な合計計算の実装とパフォーマンス比較：エラトステネスのふるいを用いて素数の合計を計算する関数を作成し、ナイーブな方法と比較することで、その圧倒的なパフォーマンス向上を実感しました。

この記事を通して、アルゴリズムがプログラムの実行速度にどれほど大きな影響を与えるか、そして効率的なアルゴリズムを選ぶことの重要性を理解していただけたことと思います。JavaScriptの基本的な構文に加え、このようなアルゴリズム的思考を身につけることは、より複雑な問題解決や高性能なアプリケーション開発において非常に強力な武器となります。

今後は、さらに高速な素数探索アルゴリズム（例：セグメント化されたエラトステネスのふるい）や、その他の基本的なアルゴリズム問題（ソート、探索など）についても深掘りしていくと、より理解が深まるでしょう。

参考資料

• エラトステネスの篩 - Wikipedia
• MDN Web Docs - JavaScript
• AtCoder Beginners Selection: ABC081B - Shift only (素数とは直接関係ありませんが、アルゴリズム学習の入り口として)