C++でピアポント素数をすべて出力する方法

この記事では、整数 n が与えられたとき、n 未満にあるすべてのピアポント素数(Pierpont Prime)を求めて出力する方法を解説します。

ピアポント素数とは

ピアポント素数とは、次の形式で表される特殊な素数のことです。

p = 2ⁱ × 3^k + 1

ここで p は素数、i と k は非負の整数です。つまり「2 のべき乗と 3 のべき乗の積に 1 を加えた数」が素数となるとき、その数をピアポント素数と呼びます。たとえば 13 = 2²×3¹+1、19 = 2¹×3²+1、37 = 2²×3²+1 であり、これらはすべてピアポント素数です。

入力例と出力例

入力: n = 50

出力: 2, 3, 5, 7, 13, 17, 19, 37

解法の考え方

この問題を解くには、条件を満たすすべての素数を見つける必要があります。そのため、次の手順で処理を進めます。

1. 2 のべき乗と 3 のべき乗を組み合わせ、2ⁱ×3^k+1 の形で表され、かつ n 未満となる候補数をすべて列挙します。
2. エラトステネスの篩を用いて、各候補が素数かどうかを判定します。
3. 候補の中から素数であるものだけを出力します。

C++での実装例

上記の解法を実装したプログラムは次のとおりです。

#include <bits/stdc++.h>
using namespace std;
void printPierpontPrimes(int n){
    bool arr[n+1];
    memset(arr, false, sizeof arr);
    int two = 1, three = 1;
    while (two + 1 < n) {
        arr[two] = true;
        while (two * three + 1 < n) {
            arr[three] = true;
            arr[two * three] = true;
            three *= 3;
        }
        three = 1;
        two *= 2;
    }
    vector<int> primes;
    for (int i = 0; i < n; i++)
    if (arr[i])
        primes.push_back(i + 1);
    memset(arr, false, sizeof arr);
    for (int p = 2; p * p < n; p++) {
        if (arr[p] == false)
            for (int i = p * 2; i < n; i += p)
                arr[i] = true;
    }
    for (int i = 0; i < primes.size(); i++)
        if (!arr[primes[i]])
        cout<<primes[i]<<"\t";
}
int main(){
    int n = 50;
    cout<<"All Pierpont Prime Numbers less than "<<n<<" :\n";
    printPierpontPrimes(n);
    return 0;
}

実行結果

All Pierpont Prime Numbers less than 50 are :
2    3    5    7    13    17    19    37