⏱️
Project Eulerの初級問題#60"Prime Pair Sets"をJavaScriptで解く

2025/11/03に公開
 はじめにProject Eulerは、プログラミングによって解くことを意図した数学的な問題を集めたウェブサイトです。今回は、問題#60 "Prime Pair Sets" の解き方について述べます。前回の問題#51 "Prime Digit Replacements" よりも難度が1段階上がっています。

https://projecteuler.net/problem=60

 問題Prime Pair Sets (素数ペアの集合)
素数 3、7、109、673 は非常に興味深い。任意の2つの素数を任意の順序で連結すると、結果は常に素数になる。例えば、7  と 109 を連結すると、7109 と 1097 はどちらも素数になる。これら4つの素数の和 792 は、この性質を持つ4つの素数の和の最小値を表す。
任意の2つの素数を連結すると別の素数になる5つの素数の和の最小値を求めなさい。

 考察この問題は、5個の素数の組を作って、その中の素数2つを連結したものが素数かどうかを繰り返し判定していくことによって解が見つかります。素数の組が4個までならば単純な方法で問題を解くことができますが、素数の組が5個になると計算量が爆発的に増大するため、1分以内で解を得ることはできません。そこで、以下の考察を行います。
素数の上限値が与えられたいないため、かなり大きな数を扱わなければならなくなる可能性がある。
連結してできる数が素数かどうかを判定する必要が生じるため、桁数が多い数を高速に判定する工夫が必要になる。
5個の素数の中から2個を選ぶ組み合わせ（順列）は 5*4=20 通りあるため、不要な組み合わせの早期発見が必要になる。
5個の素数の組を見つけるだけでなく、それに含まれる素数の和が最小であることを検証する必要がある。

 解決方針上記の考察に基づいて、以下の解決方針を立てます。
素数の判定には、問題#51と同様に「エラトステネスのふるい」を用いる。ただし、メモリ使用量を節約するため、上限値 1,000,000 を超える数の判定は別の方法で行う。その際に、同じ判定を複数回行うことがないように、結果を記録しておく。
小さな素数から順に組み合わせを作っていく。連結して素数にならないことが判明した段階で、ただちにその組み合わせを破棄して次の素数を探索に行く。
3以外の素数は、3x+1 と 3x+2 の2種類がある（ただし、x は整数）。前者と後者を連結した数は必ず3の倍数になって素数ではない。この性質を使って、素数の組み合わせを高速化する。
個々の素数の大きさに上限値を設けて探索するのではなく、5つの素数の和に上限値を設けて探索を行う。これにより、見つけた解が最小であることを検証する必要がなくなる。
上記4で設けた上限値で解が見つからなかった場合は、上限値を大きくしてやり直す。なお、解が1つ見つかったら、その解を上限値として次の解を探索する。

 プログラム構成上記の解決方針に基づいて、以下の関数を作成します。なお、言語はJavaScript(Node.js)を使用します。

 getPrimes(nMax)1 以上 nMax 未満の整数について、素数ならばtrue、そうでなければfalseの値が格納された配列を生成する。引数は配列のサイズ、戻り値は生成した配列である。配列の生成にはエラトステネスのふるいを使用し、isPrime[n] で n が素数かどうかを判定できるようにする。
function getPrimes(nMax) {
    let isPrime = Array(nMax); // 素数判定配列
    isPrime.fill(true);
    isPrime[1] = false;
    for (let n = 2; n < nMax; n++) {
        if (isPrime[n]) {
            for (let m = n * 2; m < nMax; m += n) {
                isPrime[m] = false;
            }
        }
    }
    return isPrime;
}

 checkPrime(n)整数 n が素数かどうかを判定する。引数は調べる整数、戻り値は素数ならばtrue、素数でなければfalseである。なお、この関数はグローバルなスコープに登録された素数判定配列(isPrime)と判定済マップ(exPrime)を使用する。素数判定配列はgetPrimes(nMax)で作成した配列であり、n < nMax ならば isPrime[n] の値を返却する。n >= nMax ならば自身で作成した判定済マップを参照し、このマップに記録されていれば exPrime.get(n) の値を返却し、そうでなければ試し割り法で判定した結果を判定済マップに登録後、これを返却する。
let maxPrime = 1_000_000; // 素数の最大値
let isPrime = getPrimes(maxPrime); // 素数判定配列
let exPrime = new Map(); // maxPrimeを超える判定済の数

function checkPrime(n) {
    if (n < isPrime.length) { // 素数判定配列を参照
        return isPrime[n];
    } else {
        if (exPrime.has(n)) { // 判定済マップを参照
            return exPrime.get(n);
        } else if (n % 2 == 0) { // 2で割り切れるか
            exPrime.set(n, false); // 判定済マップに記録
            return false;
        } else {
            for (let i = 3; i <= Math.sqrt(n); i += 2) {
                if (isPrime[i] && n % i == 0) { // 素数で割り切れるか
                    exPrime.set(n, false); // 判定済マップに記録
                    return false;
                }
            }
            exPrime.set(n, true); // 判定済マップに記録
            return true;
        }
    }
}

 function isFriend(n, p, pList)新規素数 p が素数リスト pList の n 番目の要素として追加可能かどうかを判定する。引数の pList は5個の素数を格納できる配列であり、戻り値は pList の最初から n-1 番目の既存素数と p を連結したものがすべて素数ならば true、1つでも素数でなければ false である。例えば、isFriend(11, 2, [3, 7]) は 711 が素数でないため false、isFriend(109, 2, [3, 7]) は 3109, 1093, 7109, 1097 のすべてが素数であるため true を返却する。なお、この関数は内部で checkPrime関数を使用している。
function isFriend(n, p, pList) {
    // 最初に素数 3x+1, 3x+2 の2種類が混在させないようにする
    if (pList[0] != 3 && n % 3 != pList[0] % 3 ||
        p > 1 && n % 3 != pList[1] % 3) {
        return false;
    }
    for (let i = 0; i < p; i++) { // pList登録済の素数を順に処理
        let ab = String(pList[i]) + String(n); // 既存+新規の順に連結
        if (!checkPrime(Number(ab))) {
            return false;
        }
        let ba = String(n) + String(pList[i]); // 新規+既存の順に連結
        if (!checkPrime(Number(ba))) {
            return false;
        }
    }
    return true;
}

 problem60(limit)整数 limit の範囲内で問題を解く。引数は素数の和の上限値、戻り値は見つかった素数の和の最小値である。ただし、範囲内で問題の条件を満たす素数の組が見つからなかった場合は null を返却する。この関数は、再帰処理を使うと少ない行数で実装できますが、初級者が直感的に理解できるように多重ループで実装しています。
function problem60(limit) { // 合計の上限値
    let pList = Array(5); // 素数リスト
    let found = false; // 素数の組が見つかったか

    for (let p0 = 2; p0 < limit; p0++) { // 0番目
        if (isPrime[p0]) {
            pList[0] = p0;
            for (let p1 = p0 + 1; p1 + p0 < limit; p1++) { // 1番目
                if (isPrime[p1] && isFriend(p1, 1, pList)) {
                    pList[1] = p1;
                    for (let p2 = p1 + 1; p2 + p1 + p0 < limit; p2++) { // 2番目
                        if (isPrime[p2] && isFriend(p2, 2, pList)) {
                            pList[2] = p2;
                            for (let p3 = p2 + 1; p3 + p2 + p1 + p0 < limit; p3++) { // 3番目
                                if (isPrime[p3] && isFriend(p3, 3, pList)) {
                                    pList[3] = p3;
                                    for (let p4 = p3 + 1; p4 + p3 + p2 + p1 + p0 < limit; p4++) { // 4番目
                                        if (isPrime[p4] && isFriend(p4, 4, pList)) {
                                            pList[4] = p4;
                                            console.log(pList);
                                            limit = p4 + p3 + p2 + p1 + p0; // 上限値更新
                                            found = true;
                                            break;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    if (found) { // 見つかった
        return limit;
    } else { // 見つからなかった
        return null;
    }
}

 おわりに素数の和の上限値を10,000に設定した場合は解が見つかりません。しかし、以下のように上限値を100,000に設定して実行すると、最初に [3, 3119, 9887, 36263, 48731] がコンソールに表示されますが、これは最小の組ではありません。その後、和がより小さな組が探索されていき、最終的に正解に到達します。プログラムの実行時間は、ノートPC (Intel(R) Core(TM) i5-8250U CPU) 上の Node.js v24 で約20秒です。これは決して速いとは言えませんが、許容できる速度だと思います。
console.log(problem60(10_000));

 関連記事Project Eulerの初級問題#51"Prime Digit Replacements"をJavaScriptで解く

https://zenn.dev/uinoue/articles/cd268868681432
Project Eulerの初心者向け問題をPythonで解く

https://zenn.dev/uinoue/articles/9979461e883245
はじめに

問題

考察

解決方針

プログラム構成

getPrimes(nMax)

checkPrime(n)

function isFriend(n, p, pList)

problem60(limit)

おわりに

関連記事

Discussion
