C++で素数トリプレット（三つ組の素数）をすべて求める方法

問題の概要

この問題では、ある数値 N が与えられ、N未満のすべての素数トリプレットを見つけて出力することが求められます。

素数トリプレットとは

素数トリプレットとは、3つの素数からなる組のことで、次のいずれかの形で表されます。

• (p, p+2, p+6)
• (p, p+4, p+6)

5以上の素数は必ず「6k±1」の形で表されるため、素数はこのパターンに従って三つ組にグループ化されます。

入出力例

入力：N = 13
出力：5 7 11

解法のアプローチ

この問題を解くには、まずN以下のすべての素数を求め、その後トリプレットの条件に合致するかどうかを確認します。素数の列挙にはエラトステネスの篩を用いることで、効率的に処理できます。

1. エラトステネスの篩でN以下の素数をすべて求める。
2. 各数値 i について、(i, i+2, i+6) または (i, i+4, i+6) の3つがすべて素数かどうかを判定する。
3. 条件を満たす組をすべて出力する。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
void findPrimes(int n, bool prime[]) {
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * 2; i <= n; i += p)
            prime[i] = false;
        }
    }
}
void printPrimeTriplets(int n) {
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
    findPrimes(n, prime);
    for (int i = 2; i <= n-6; ++i) {
        if (prime[i] && prime[i + 2] && prime[i + 6])
            cout<<i<<"\t"<<(i+2)<<"\t"<<(i+6)<<endl;
        else if (prime[i] && prime[i + 4] && prime[i + 6])
            cout<<i <<"\t"<<(i + 4)<<"\t"<<(i + 6)<<endl;
    }
}
int main() {
    int N = 15;
    cout<<"Prime Triplets Less than "<<N<<" are :\n";
    printPrimeTriplets(N);
    return 0;
}

出力結果

Prime Triplets Less than 15 are :
5   7   11
7   11   13

計算量について

エラトステネスの篩による素数生成の時間計算量は O(N log log N)、トリプレットの判定は配列を一度走査するだけなので O(N) です。したがって、全体の計算量は O(N log log N) となり、非常に効率的なアルゴリズムといえます。