C++で学ぶベルトランの仮説：素数の存在を保証する定理と実装方法

ベルトランの仮説（Bertrand's Postulate）とは、「3より大きい任意の整数 n に対して、n と 2n−2 の間に少なくとも1つの素数 p が存在する」ことを主張する数学の定理です。素数が数直線上にどれほど密に分布しているかを示す重要な結果として知られています。

ベルトランの仮説の定式化

n < p < 2n − 2

ここで、n は n > 3 を満たす整数、p は素数を表します。

素数とは、正の約数が 1 とその数自身のみである自然数のことです。たとえば、2、3、5、7、11 などが素数の代表例です。

また、ベルトランの仮説には、より扱いやすい緩い定式化もあります。

n < p < 2n　（すべての n > 1 に対して成り立つ）

この形式では「1より大きい任意の整数 n に対して、n と 2n の間に必ず素数が存在する」と述べられており、証明や実装の際にシンプルに扱えます。

具体例

入力

5

出力

7

解説

5 と 2×5 = 10 の間に存在する素数を求めます。この範囲内の素数は 7 です。

入力

11

出力

13, 17, 19

解説

11 と 2×11 = 22 の間に存在する素数を求めます。この範囲には 13、17、19 の3つの素数が含まれます。

ベルトランの仮説を使った素数探索プログラム（C++）

以下は、与えられた数 n に対して、n と 2n の間に存在する素数を出力する C++ プログラムです。

#include <iostream>
using namespace std;

// 素数判定して出力する関数
void printPrime(int n) {
    int flag = 0;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) // i が n の約数の場合
            flag++;
    if (flag == 0)
        cout << n << " ";
}

int main() {
    int n = 22;
    cout << "Prime numbers in range (" << n << ", " << 2*n << ") :\t";
    for (int p = n + 1; p < 2 * n - 2; p++)
        printPrime(p);
    return 0;
}

実行結果

Prime numbers in range (22, 44) : 23 29 31 37 41

プログラムの解説

このプログラムの仕組みは以下の通りです。

• printPrime 関数：引数として受け取った数が素数かどうかを判定します。2 から √n までの整数で順に割り切れるかを確認し、約数が1つも見つからなければ（flag が 0 のままなら）その数は素数であるため出力します。
• main 関数：n+1 から 2n−2 未満までの各整数について printPrime を呼び出し、範囲内の素数をすべて表示します。

たとえば n = 22 の場合、22 から 44 の範囲に含まれる素数 23、29、31、37、41 が出力されます。これはベルトランの仮説が実際に成立していることを示す好例といえます。