C++で指定した数以下のすべての素数四つ組を出力する方法

この記事では、正の整数 N が与えられたとき、N 以下に存在するすべての「素数四つ組」を見つけて出力する方法を解説します。

素数四つ組とは？

素数四つ組とは、{p, p⁺², p⁺⁶, p⁺⁸} という形で表される4つの素数の集合のことです。代表例として、「5、7、11、13」の組み合わせが挙げられます。

具体例を使って問題を確認してみましょう。

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

解法アプローチ

1. 単純なアプローチ

最もシンプルな方法は、すべての候補 p に対して、p、p⁺²、p⁺⁶、p⁺⁸ がそれぞれ素数かどうかを個別に判定していくことです。この方法は実装が簡単ですが、同じ数に対して何度も素数判定を繰り返すため計算コストが高く、大規模な入力では処理が重くなるという欠点があります。

2. 効率的なアプローチ（エラトステネスの篩）

より効率的なのが、エラトステネスの篩を利用する方法です。あらかじめ一定範囲までのすべての素数を求めて配列に格納しておけば、各数値が素数かどうかを O(1) で判定できます。あとは配列を走査しながら、p、p⁺²、p⁺⁶、p⁺⁸ の4つがすべて素数である場合に出力するだけです。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
bool prime[MAX];
void primeNumberGenerator() {
    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;
        }
    }
}
void printPrimeQuadruplet(int n) {
    for (int i = 0; i < n - 7; i++) {
        if (prime[i] && prime[i + 2] && prime[i + 6] && prime[i + 8]) {
            cout<<i<<" "<<i+2<<" "<<i+6<<" "<<i+8<<endl;
        }
    }
}
int main() {
    primeNumberGenerator();
    int n = 42;
    cout<<"All prime Quadruplets are :\n";
    printPrimeQuadruplet(20);
    return 0;
}

コードのポイント

• primeNumberGenerator()：エラトステネスの篩を実装した関数です。bool 型配列を使い、MAX 未満のすべての整数について素数かどうかを事前に記録します。
• printPrimeQuadruplet(n)：i + 8 が n を超えないようにループ範囲を制御し、i、i+2、i+6、i+8 の4つがすべて素数の場合に四つ組として出力します。

実行結果

上記のコードを実行すると、次の出力が得られます。

5 7 11 13
11 13 17 19

このように、エラトステネスの篩で素数表を事前構築しておくことで、N 以下のすべての素数四つ組を効率よく列挙できます。