2018年12月の時点で「素数として確認された最大の数」は 282,589,933 − 1 である。この素数は24,862,048 桁の長さを持ち、2018年12月に Great Internet Mersenne Prime Search (GIMPS) によって発見された。
素数？そ～すぅね...はい、どうもボクです。というわけで、今回は、Java のお話です。
素数を求めるプログラム
PHPで、求めてる人がいらっしゃいました。
んじゃぁ、Javaでやってみようってことで、Javaの標準APIである、BigIntegerクラスに、nextProbablePrime() ってメソッドがあるんですな。
BigInteger java.math.BigInteger.nextProbablePrime()
nextProbablePrime
public BigInteger nextProbablePrime()
このBigIntegerより大きい最初の整数(おそらく素数)を返します。
このメソッドの返す数が合成数である確率は2-100を超えません。このメソッドは検索時に素数をスキップしません。
pを返す場合、this < q < pが成り立つような素数qはありません。
戻り値:このBigIntegerより大きい最初の整数(おそらく素数)。
例外:ArithmeticException - this < 0であるか、thisが大きすぎる場合。
導入されたバージョン:1.5
ん？なんか、微妙な空気を醸し出している...駄目な予感が...
⇧ 上記サイト様のスライドによりますと、まぁ、大丈夫であろうと。 内部的には、「ミラー - ラビン素数判定法」ってものを使ってるらしいと。
2023年1月29日（日）編集：↓ ここから
コメントいただき、計算が間違ってましたので、再計算いたしました。
2-100 っていうことは、1.0069555500567189 % で、失敗するってことかしら？
実際に、計算してみた。
double base = 2;
double exponent = Double.valueOf("1") / Double.valueOf("100");
System.out.println(Math.pow(base, exponent));
うん、そういうことらしい、って... ...
え？ 100回やったら、1回は素数じゃない値が返却される可能性があるってこと？
駄目じゃね？
精度低過ぎでしょ...
ちなみに、double はプリミティブ型ということで、
⇧ 上記サイト様が詳しいです。
Doubleクラスは、プリミティブ型doubleの値をオブジェクトにラップします。Double型のオブジェクトには、型がdoubleの単一フィールドが含まれます。
https://docs.oracle.com/javase/jp/8/docs/api/java/lang/Double.html
⇧ Double型はdoubleのラッパークラス。
2023年1月29日（日）編集：↑ ここまで
2023年1月29日（日）追記：↓ ここから
コメントいただたき、2-100 の計算が間違ってたので、再計算しました。
double base = 2;
double exponent = Double.valueOf("-100");
System.out.println(Math.pow(base, exponent));
double base = 2;
double exponent = Double.valueOf("100");
System.out.println(1/Math.pow(base, exponent));
⇧ だいぶ小さい値ということが分かりました。
指数表記しないで表示。
double base = 2;
double exponent = Double.valueOf("100");
System.out.println(BigDecimal.valueOf(1/Math.pow(base, exponent)).toPlainString());
失敗する確率は、0.0000000000000000000000000000007888609052210118%となり、精度は高いことが分かりました。
10のマイナス1乗は「0.1（＝1/10）」です。マイナス〇乗の計算では「a－m=1/am」のように「分母をam」とする分数になります。よって、10のマイナス1乗は「101を分母、分子は1」なので、1/101=1/10=0.1です。10のマイナス2乗は「0.01」、10のマイナス3乗は「0.001」になります。
2023年1月29日（日）追記：↑ ここまで
実際にやってみた
Eclipseを起動して、適当にJavaプロジェクトを作成。クラスも作成。
そしたらば、今回は、結果をファイルに書き込みたいので、適当にフォルダを作成し、ファイルも作成。（Maven や、Gradle なんかのビルドツールでプロジェクトを作成してる場合は、プロジェクトのフォルダの構成とかも変わってくると思われます。）
今回、「FunctionIFTest」ってJavaプロジェクトを作成しているので、プロジェクトディレクトリ直下に、「file」というフォルダを作成しました。
「file」フォルダ直下に、ファイルを作成で。
適当なファイルを作成で。
今回は、1000個の素数で試しました。（時間かかってもOKよって人は、数を増やしてトライしてみよう。）
4桁の素数を出すのでも調べるのに時間がかかってしまった、世界記録は、24,862,048 桁 というのに（涙）。
ソースコードはこんな感じで。
package main;
import java.io.IOException;
import java.math.BigInteger;
import java.nio.charset.Charset;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.OpenOption;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.util.List;
import java.util.logging.Logger;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Eratoshenes {
final static Logger logger = Logger.getLogger("EratoshenesLogging");
final static String PRIME_NUM_OUTPUT_FILE_PATH = "file/primeNumber.txt";
public static void main(String[] args) {
// TODO 自動生成されたメソッド・スタブ
List<String> list = takePrimeList(new BigInteger("1000"));
fileWrite(Paths.get(PRIME_NUM_OUTPUT_FILE_PATH), list, StandardCharsets.UTF_8,
StandardOpenOption.TRUNCATE_EXISTING);
System.out.println("素数の数： " + list.size());
}
/**
* 指定した範囲で素数を求めて、テキスト（文字列）のListに変換するメソッド
* @param number 指定範囲の整数
* @return 素数のテキスト（文字列）
*/
public static List<String> takePrimeList(BigInteger number) {
return Stream.iterate(BigInteger.valueOf(2), BigInteger::nextProbablePrime)
.limit(number.longValue())
.peek(x -> {
System.out.println(x);
}).map(bigInt -> bigInt.toString())
.collect(Collectors.toList());
}
/**
* ファイルに書き込むメソッド
* @param outPutPath 出力先のファイルパス
* @param lines 出力したいテキスト（文字列）
* @param cs 文字コード
* @param options 出力のオプション
*/
public static void fileWrite(Path outPutPath, Iterable<? extends CharSequence> lines, Charset cs,
OpenOption... options) {
try {
Files.write(outPutPath, lines, cs, options);
} catch (IOException e) {
// TODO 自動生成された catch ブロック
e.printStackTrace();
}
}
}
んで、実行してみる。
テキストファイルに出力されました。Loggerクラスのインスタンスとか用意しておきながら、使ってないや...
Stream API の limit() が無いと無限ループ？になってしまうようなので、どこまで処理するか制限を設ける必要があるようです。まぁ、このへんは決め打ちで指定するしかないかと。（だって、素数がいくつあるかを調べたいんだから、事前に素数がいくつあるかなんて分かるわけないしね）
クラス名を、Eratoshenes とかにしちゃったけど、全然、「エラトステネスの篩」になってないっす（涙）。
ファイルの2GBの壁に関する問題は、
⇧ 上記サイト様によりますと、java.nio.file.Files パッケージのcopy メソッドなら問題なく回避できるらしいです。
ファイルパスとかは、
⇧ 上記サイト様を参考にさせていただきました。
ちなみに、Stream API ですが、
⇧ 上記サイト様が詳しいです。
発展途上ということで、Java 9 とかでちょこっと機能が追加されてるそうです。
Stream API の peek() メソッドとかってデバッグ用途だったんすね。forEach() と違って、戻り値を戻せる状態のままで処理してくれるのはありがたいかな。
Wikipedia さんによりますと、
⇧ かなり、たくさんのアルゴリズムがあるらしい。ネットとかの情報だと「エラトステネスの篩」が多いかな。何を使えば良いのかサッパリですわ...
まぁ、何て言うか、 いつもながら、モヤモヤ感が半端ない...数学の知識ないと厳しい感じがしてならない...
とりあえず、BigInteger クラスの nextProbablePrime() メソッドは、あんまりイケてないらしいということですかね。
今回はこのへんで。
