C++でN以下のすべてのプロス素数（Proth素数）を出力する方法

問題概要

この問題では、整数Nが与えられ、N以下のすべてのプロス素数（Proth Prime）を求めて出力することを目標とします。

プロス素数とは？

プロス数（Proth Number）とは、次の形式で表すことができる正の整数のことです。

N = k × 2p + 1

ここで、kは奇数の正整数、pは正の整数であり、さらに次の条件を満たす必要があります。

2p > k

そして、このプロス数の中で素数であるものをプロス素数と呼びます。代表例としては、3、5、13などが挙げられます。

具体例

入力：N = 23
出力：3, 5, 13, 17

解法の考え方

この問題は、以下の手順で解くことができます。

1. エラトステネスの篩（Sieve of Eratosthenes）を使って、N以下のすべての素数を事前に列挙します。
2. 各数値nについて、「n − 1」が奇数kと2の冪乗の積（k × 2^p）として表せるかどうかを判定します。
3. その条件を満たし、かつ素数である数値だけを出力します。

2の冪乗の判定には、ビット演算を利用した「x && !(x & (x − 1))」という定番のテクニックを使うことで、効率よくチェックできます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int prime[1000];
void SieveOfEratosthenes(int n){
    for (int i = 1; i <= n + 1; i++)
        prime[i] = true;
    prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
}
bool isTwosExponent(int n){
    return (n && !(n & (n - 1)));
}
bool isaProthNumber(int n){
    int k = 1;
    while (k < (n / k)) {
        if (n % k == 0) {
            if (isTwosExponent(n / k))
                return true;
        }
        k = k + 2;
    }
    return false;
}
bool isaProthPrime(int n){
    if (isaProthNumber(n - 1)) {
        if(prime[n])
            return true;
        else
            return false;
    }
    else
        return false;
}
int main(){
    int n = 23;
    cout<<"Proth Prime Numbers less than or equal to "<<n<<" :\n";
    SieveOfEratosthenes(n);
    for (int i = 1; i <= n; i++)
        if (isaProthPrime(i))
            cout<<i<<"\t";
    return 0;
}

実行結果

上記のプログラムをN = 23として実行すると、次のような出力が得られます。

Proth Prime Numbers less than or equal to 23 are −
3 5 13 17

計算量と注意点

全体の計算量は、エラトステネスの篩の部分がO(N log log N)、各数値のプロス数判定がおおよそ√N程度のループになるため、Nがある程度大きくなっても高速に動作します。ただし、サンプルコードでは素数を管理する配列のサイズが固定されているため、より大きなNを扱いたい場合は配列サイズを適宜拡張してください。