JavaScriptで指定範囲内の特定の距離を持つk-素数ペアを見つける方法

k-素数（K-Prime）とは

自然数のうち、素因数を重複込みで数えてちょうどk個持つものを「k-素数（k-prime）」と呼びます。

たとえば4の場合、素因数は2だけですが、4 = 2 × 2 と分解できるため、2が2回カウントされます。このことから4は2-素数であるといえます。

同様に、8 = 2 × 2 × 2 と3つの素因数に分解できるため、8は3-素数ということになります。

問題の概要

今回は、次の3つの引数を受け取るJavaScript関数を実装します。

• k：素因数の個数（重複込み）
• step：求めるペア間の距離（間隔）
• range：探索対象となる範囲［開始値, 終了値］

この関数は、指定された範囲内に存在し、かつ互いの距離がちょうどstepと一致するk-素数のペアを「配列の配列」として返す必要があります。

コード例

以下が実際のコードです。

const k = 2;
const step = 2;
const range = [0, 50];
const kPrimeSteps = (k = 1, step = 1, [start, end]) => {
    const res = [];
    let i = start;
    const findLen = (n = 1) => {
        let count = 0, i = 2;
        while (i * i <= n) {
            while (n % i === 0) {
                count++;
                n /= i;
            }
            i++;
        }
        if (n > 1) count++;
        return count;
    }
    while (i <= end - step) {
        if ((findLen(i) == k && findLen(i+step) == k))
        res.push([i, i+step]);
        i++;
    }
    return res;
};
console.log(kPrimeSteps(k, step, range));

アルゴリズムのポイント

内部関数 findLen(n) は、試し割り法によってnの素因数の個数（重複込み）を求めます。2から√nまで順に割り切れるかどうかを確認しながらカウントし、最後に残った1より大きい数も素因数として加算します。これにより、効率よくk-素数かどうかを判定できます。

続いて、start から end − step まで各数値iについて「i自身」と「i + step」の両方がk-素数であるかをチェックし、条件を満たす場合はペアとして結果配列に追加していきます。

出力結果

上記のコードを実行すると、コンソールには以下が出力されます。

[ [ 4, 6 ], [ 33, 35 ] ]

この結果から、範囲0〜50の中で距離2を持つ2-素数のペアは [4, 6] と [33, 35] の2組であることがわかります。

• 4 = 2 × 2（2-素数）、6 = 2 × 3（2-素数）→ 距離2 ✓
• 33 = 3 × 11（2-素数）、35 = 5 × 7（2-素数）→ 距離2 ✓

このように、素因数の個数判定と間隔チェックを組み合わせることで、任意の範囲・距離・kの値に対応した柔軟な検索処理を実現できます。