【JavaScript】合計が指定した数値になるすべての素数ペアを見つける方法

問題の概要

JavaScriptで関数を作成します。この関数は引数として数値 n を受け取り、合計すると n になり、しかも両方が素数であるような数値ペアをすべて配列として返す必要があります。

例えば、入力が 26 の場合、「23 + 3」と「19 + 7」はいずれも合計が 26 で、かつ両方とも素数であるため、該当するペアとなります。

コード例

以下がその実装コードです。

const num = 26;
const isPrime = (n) => {
    if (n % 2 === 0) return false;
    let sqrtn = Math.sqrt(n)+1;
    for (let i=3; i < sqrtn; i+=2) {
        if (n % i === 0) return false;
    }
    return true;
}
const primeList = (a) => {
    if (isPrime(a)) return a; else return false;
};
const generateNumbers = (n) => {
    let num = (n % 2 === 0) ? (n -1) : n;
    let list = []
    for (let i = num; i > 3; i-=2)
        list.push(i);
    list.push(3,1);
    return list;
}
const calculate = (num, list, results) => {
    if (list.length === 0) return results;
        let item = list.shift();
    let itemPairIndex = list.indexOf(num - item);
    if (itemPairIndex !== -1) {
        let itemPair = list.splice(itemPairIndex,1)
        results.push(item+"+"+itemPair);
    }
    return calculate(num, list, results);
}
const findprimeSum = (num) => {
    const pairs = [];
    const list = generateNumbers(num).filter(primeList);
    return calculate(num, list, []);
}
console.log(findprimeSum(num));

出力結果

[ '23+3', '19+7' ]

コードの解説

• isPrime： 与えられた数値が素数かどうかを判定する関数です。まず偶数を除外し、その後 3 から平方根までの奇数で割り切れるかを確認することで、無駄な計算を省きながら効率的に判定しています。
• generateNumbers： 候補となる奇数のリストを生成します。偶数同士の和で目的の数にならないケースを考慮し、奇数のみを対象としています。
• primeList： filter のコールバックとして機能し、生成したリストから素数だけを抽出します。
• calculate： リスト内の各素数について、「num との差に相当する素数」が残りのリストに存在するかを再帰的に確認し、存在すればペアとして結果に追加します。マッチ済みの数値はリストから削除されるため、同じペアが重複して出力されることはありません。

このように、素数判定とペア探索を組み合わせることで、合計が指定した数値になるすべての素数ペアを効率よく求めることができます。