【C++】メルセンヌ素数を求めるプログラムの作り方を解説

メルセンヌ素数とは

数学におけるメルセンヌ素数とは、「2の冪乗から1を引いた値」に該当する素数のことです。すなわち、ある整数 n に対して Mn = 2ⁿ − 1 の形で表される素数を指します。

本記事では、入力された正の整数 n 未満のメルセンヌ素数をすべて出力するC++プログラムの実装方法を解説します。

メルセンヌ素数となる指数 n は 2, 3, 5, 7, … と続きます。これらに対応するメルセンヌ素数は、それぞれ 3, 7, 31, 127 です。

アルゴリズム

メルセンヌ素数を求める基本的な手順は以下のとおりです。

1. 与えられた数 n 以下のすべての素数を生成する（エラトステネスの篩を利用）
2. 2^n − 1 の形の各数について、素数であるかどうかを判定する

C++による実装例

以下のコードでは、まずエラトステネスの篩を用いて n までの素数表を作成し、その後「2の冪乗から1を引いた数」が素数表中に存在するかを順番に確認しています。

#include <iostream>
#include <algorithm>
using namespace std;

// エラトステネスの篩で n 以下の素数表を生成
void generatePrimes(bool *primes, int n){
    fill(primes, primes + n + 1, true);
    for (int p = 2; p * p <= n; ++p) {
        if (primes[p] == true) {
            for (int i = p * 2; i <= n; i += p) {
                primes[i] = false;
            }
        }
    }
}

// n 未満のメルセンヌ素数を出力
void mersennePrimes(int n){
    bool primes[n + 1];
    generatePrimes(primes, n);
    for (int i = 2; ((1 << i) - 1) <= n; ++i) {
        int num = (1 << i) - 1;
        if (primes[num]) {
            cout << num << " ";
        }
    }
    cout << endl;
}

int main(){
    int n = 100;
    cout << "Mersenne primes numbers till " << n << endl;
    mersennePrimes(n);
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

Mersenne primes numbers till 100
3 7 31

この例では n = 100 を指定しているため、100 未満のメルセンヌ素数である 3, 7, 31 のみが出力されます。次のメルセンヌ素数 127 は 100 を超えるため、ここでは表示されません。

補足：可変長配列について

サンプルコード内の bool primes[n + 1]; は可変長配列（VLA）と呼ばれる機能で、GCC などの一部のコンパイラでは利用できますが、標準C++の規格には含まれていません。移植性を重視する場合は、std::vector<bool> の使用を検討するとよいでしょう。