C/C++プログラミングで学ぶスーパー素数の求め方と実装例

スーパー素数とは？

スーパー素数（super-prime）とは、すべての素数を小さい順に並べた列の中で、素数番目に位置する素数のことです。「高階素数（higher-order primes）」と呼ばれることもあります。スーパー素数の例としては、3、5、11、17 などが挙げられます。

具体例：13未満のスーパー素数を求める

入力：

13

出力：

3, 5, 11

解説：13未満のスーパー素数を求めるには、まず13未満の素数をすべて列挙します。13未満の素数は「2, 3, 5, 7, 11, 13」です。ここで 2 は素数なので、2番目に位置する素数（3）がスーパー素数となります。同様に、3番目の素数は 5、5番目の素数は 11 であるため、これらもスーパー素数に該当します。

スーパー素数を求めるアルゴリズム

与えられた数未満のスーパー素数をすべて求める手順は以下の通りです。

1. 対象の数未満の素数をすべて求め、配列に格納する。
2. 配列の中から、位置（インデックス）が素数と一致する要素だけを出力する。

つまり、2番目、3番目、5番目、7番目、11番目、13番目…に位置する素数だけを取り出せば、それがスーパー素数の列になります。

C++による実装例

以下のコードでは、エラトステネスの篩（ふるい）を使って n までの素数をすべて判定し、その後、素数を配列に格納して「インデックス+1 が素数である」要素だけを出力しています。

#include<iostream>
using namespace std;
bool SieveOfEratosthenes(int n, bool isPrime[]) {
    isPrime[0] = isPrime[1] = false;
    for (int i=2; i<=n; i++)
        isPrime[i] = true;
    for (int p=2; p*p<=n; p++) {
        if (isPrime[p] == true) {
            for (int i=p*2; i<=n; i += p)
                isPrime[i] = false;
        }
    }
}
void superPrimes(int n) {
    bool isPrime[n+1];
    SieveOfEratosthenes(n, isPrime);
    int primes[n+1], j = 0;
    for (int p=2; p<=n; p++)
        if (isPrime[p])
    primes[j++] = p;
    for (int k=0; k<j; k++)
        if (isPrime[k+1])
    cout << primes[k] << " ";
}
int main() {
    int n = 343;
    cout << "Super-Primes less than "<< n << " are :"<<endl;
    superPrimes(n);
    return 0;
}

実行結果

Super-Primes less than 343 are :
3 5 11 17 31 41 59 67 83 109 127 157 179 191 211 241 277 283 331

まとめ

スーパー素数は「素数の列における素数番目の素数」であり、エラトステネスの篩を2段階に分けて適用することで効率よく求められます。計算量は O(n log log n) 程度に収まるため、比較的大きな n に対しても高速に動作するのが特徴です。