Javaでメルセンヌ数(2の冪-1)を求める方法を記載します。
メルセンヌ数についてはWikipediaを参考にしてください。
前提
対応
2の冪-1が整数となる値を求めるために次の式を使用します。
private static boolean isMersenne(int value) {
return log2(value + 1) % 1 == 0;
}
public static double log2(int value) {
return Math.log(value) / Math.log(2);
}
解説
2の冪-1 = メルセンヌ数
ですので、式変形して2の冪=メルセンヌ数+1
と変形できます。2の冪数の計算については、次の式で求められます。
log2(value + 1);
public static double log2(int value) {
return Math.log(value) / Math.log(2);
}
あとは、求めた冪数が整数であることを求めます。今回は値 % 1 == 0
で整数を求めました。
private static boolean isMersenne(int value) {
return log2(value + 1) % 1 == 0;
}
メルセンヌ素数を求める
メルセンヌ数に条件を追加するとメルセンヌ素数を求められます。素数は次のメソッドで求められます。詳しい原理については他の方のブログを参考にしてください。
public static boolean isPrime(int value) {
if (value <= 1) {
return false;
}
if (value <= 3) {
return true;
}
for (int i = 2; i <= Math.sqrt(value); i++) {
if (value % i == 0) {
return false;
}
}
return true;
}
ソースコード
終わりに
メルセンヌ数も素数も普段求めないから頭が回らないですね。解く機会があったので今回のブログにしました。
類似情報