JavaScriptでメルセンヌ素数を判定する方法

数学において、メルセンヌ素数とは、ある整数 n に対して M(n) = 2^n − 1 という形で表すことができ、かつ実際に素数である数のことを指します。

たとえば、最初の4つのメルセンヌ素数は次のとおりです。

• 3 = 2^2 − 1
• 7 = 2^3 − 1
• 31 = 2^5 − 1
• 127 = 2^7 − 1

本記事では、JavaScriptの関数を使って、与えられた数がメルセンヌ素数であるかどうかを判定する方法を解説します。

判定のアプローチ

メルセンヌ素数の判定には、次の2つの条件を確認する必要があります。

1. その数が素数であること
2. その数に1を加えた値が、2の累乗であること

まず素数判定を行う関数を作成し、続いて「数 + 1」が2の累乗になるまで2で割り続けることで、メルセンヌ素数かどうかを確認します。

サンプルコード

const isPrime = num => {
    let i = 2;
    while(i <= num / 2){
        if(num % i++ === 0){
            return false;
        };
    };
    return true;
}
const mersennePrime = num => {
    if(!isPrime(num)){
        return false;
    };
    let n = num + 1;
    while(n !== 1){
        if(n % 2 !== 0){
            return false;
        };
        n /= 2;
    };
    return true;
};
console.log(mersennePrime(31));
console.log(mersennePrime(127));
console.log(mersennePrime(3));
console.log(mersennePrime(37));
console.log(mersennePrime(87));
console.log(mersennePrime(7));

コードのポイント

isPrime 関数は、2からその数の半分まで順番に割っていき、余りが0になる約数が存在すれば素数ではないと判断します。

mersennePrime 関数では、まず素数判定を行い、素数でなければ即座に false を返します。その後、「元の数 + 1」を繰り返し2で割っていき、途中で奇数が出現した場合は2の累乗ではないため false を返します。最終的に値が1になれば、2^n − 1 の形で表せるメルセンヌ素数であると判定できます。

実行結果

コンソールへの出力は次のようになります。

true
true
true
false
false
true

このように、31・127・3・7 はメルセンヌ素数として正しく判定され、37 は素数ですが2の累乗から1を引いた形ではないため false、87 はそもそも素数ではないため false となります。