C++で指定された範囲内の最大の双子素数を見つける方法

問題概要

この問題では、2つの値 lValue と hValue が与えられ、指定された範囲内で最大の双子素数（ツイン素数）を見つけることが求められます。

双子素数とは、両方とも素数であり、その差が2であるような数のペアを指します。例えば (3, 5)、(11, 13)、(71, 73) などが代表例です。

具体例で問題を確認してみましょう。

入力 : lValue = 65, rValue = 100
出力 : 71, 73

範囲 [65, 100] の中で、差が2となる素数ペアは (71, 73) のみであり、これが答えとなります。

解決アプローチ

アプローチ1: 単純なループによる探索

最もシンプルな解決策は、rValue - 2 から lValue まで逆順にループし、各ペア i と (i+2) が双子素数かどうかを順番にチェックしていく方法です。最初に見つかったペアが範囲内の最大の双子素数となります。

アプローチ2: エラトステネスの篩を活用する方法

より効率的な方法として、まず範囲内のすべての素数をエラトステネスの篩で事前に求めておき、その後、大きい方から順に i と (i-2) が両方とも素数であるペアを探します。これにより素数判定を高速化できます。

実装例

以下は、エラトステネスの篩を用いた解決策の動作を示すC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
void findLargestTwins(int lValue, int uValue) {
    bool primes[uValue + 1];
    memset(primes, true, sizeof(primes));
    primes[0] = primes[1] = false;
    for (int p = 2; p <= floor(sqrt(uValue)) + 1; p++) { 
        if (primes[p]) {
            for (int i = p * 2; i <= uValue; i += p)
            primes[i] = false;
        }
    }
    int i;
    for (i = uValue; i >= lValue; i--) {
        if (primes[i] && (i - 2 >= lValue && primes[i - 2] == true)) {
            break;
        }
    }
    if(i >= lValue )
        cout<<"Largest twins in given range: ("<<(i-2)<<", "<<i<<")";
    else 
        cout<<"No Twins possible";
}
int main(){
   int lValue = 54;
   int uValue = 102;
   findLargestTwins(lValue, uValue);
   return 0;
}

出力結果

Largest twins in given range: (71, 73)

コードの解説

このプログラムの処理の流れは以下の通りです。

1. 素数表の作成： memset を使って primes 配列をすべて true で初期化し、0と1を素数ではないとしてマークします。その後、2から √uValue+1 までの各数値について、その倍数を素数ではないとマークしていきます（エラトステネスの篩）。

2. 最大の双子素数の探索： 上限値 uValue から下限値 lValue に向かって逆順にループし、i と i-2 が両方とも素数である最初のペアを見つけたらループを終了します。

3. 結果の出力： 双子素数のペアが見つかった場合はそのペアを出力し、見つからなかった場合は「No Twins possible」と出力します。

まとめ

この問題は、エラトステネスの篩を用いることで範囲内の素数判定を効率的に行い、大きい方から順に双子素数のペアを探索することで解くことができます。計算量は素数表の作成に O(n log log n)、探索に O(n) となり、非常に効率的なアルゴリズムです。