C++でn番目の平衡素数（バランス素数）を求める方法

平衡素数とは

平衡素数（Balanced Prime）とは、直前の素数と直後の素数までの距離（差）が等しい素数のことです。言い換えれば、前後にある最も近い素数の平均値に一致する素数を指します。

ある素数が平衡素数であるためには、次の式を満たす必要があります。

P_n = (P_n-1 + P_n+1) / 2

ここで、nは順序付けられた素数列におけるP_nのインデックス（順位）を表します。

素数の順序付き集合：2, 3, 5, 7, 11, 13, …

最初のいくつかの平衡素数は、5, 53, 157, 173, … です。

問題の概要

この問題では、数値nが与えられ、n番目の平衡素数を求めることが求められます。

具体例を見てみましょう。

入力 : n = 3
出力 : 157

解法のアプローチ

まず、エラトステネスの篩を用いて素数を生成し、ベクター（動的配列）に格納します。その後、各素数について「前後の素数の平均値と一致するか」を順に判定し、平衡素数であればカウントを1つ増やします。カウントがnに達した時点で、その素数の値を返して処理を終了します。

C++での実装例

#include<bits/stdc++.h>
#define MAX 501
using namespace std;
int balancedprimenumber(int n){
    bool prime[MAX+1];
    memset(prime, true, sizeof(prime));
    for (int p = 2; p*p <= MAX; p++){
        if (prime[p] == true)
        {
            for (int i = p*2; i <= MAX; i += p)
            prime[i] = false;
        }
    }
    vector<int> v;
    for (int p = 3; p <= MAX; p += 2)
    if (prime[p])
    v.push_back(p);
    int count = 0;
    for (int i = 1; i < v.size(); i++){
        if (v[i] == (v[i+1] + v[i - 1])/2)
        count++;
        if (count == n)
        return v[i];
    }
}
int main(){
    int n = 3;
    cout<<balancedprimenumber(n)<<endl;
    return 0;
}

出力

157

コードのポイント

このプログラムでは、まずブール型の配列を使ってエラトステネスの篩を実装し、MAX（501）以下の素数を効率的に抽出しています。奇数のみをベクターに格納することで、無駄な計算を省いています。その後、隣接する3つの素数の関係を調べることで平衡素数を判定し、n番目に到達した時点で結果を返します。計算量は篩の部分でO(MAX log log MAX)程度に抑えられるため、十分に高速に動作します。