Java 素数を求める、標準APIのBigIntegerクラスのnextProbablePrime() である程度はイケるらしい...いや駄目かも

f:id:ts0818:20190817104448p:plain

2018年12月の時点で「素数として確認された最大の数」は 282,589,933 − 1 である。この素数は24,862,048 桁の長さを持ち、2018年12月に Great Internet Mersenne Prime Search (GIMPS) によって発見された。

巨大な素数の一覧 - Wikipedia

素数?そ~すぅね...はい、どうもボクです。というわけで、今回は、Java のお話です。

 

素数を求めるプログラム

PHPで、求めてる人がいらっしゃいました。 

crieit.net

んじゃぁ、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

BigInteger (Java Platform SE 8)

ん?なんか、微妙な空気を醸し出している...駄目な予感が... 

www.slideshare.net

⇧  上記サイト様のスライドによりますと、まぁ、大丈夫であろうと。 内部的には、「ミラー - ラビン素数判定法」ってものを使ってるらしいと。

2-100 っていうことは、1.0069555500567189 % で、失敗するってことかしら?

実際に、計算してみた。

    double base = 2;
    double exponent = Double.valueOf("1") / Double.valueOf("100");
    System.out.println(Math.pow(base, exponent));

f:id:ts0818:20190817170753p:plain

うん、そういうことらしい、って... ...

え? 100回やったら、1回は素数じゃない値が返却される可能性があるってこと?

駄目じゃね?

精度低過ぎでしょ...

 

ちなみに、double 型については、

engineer-club.jp

⇧  上記サイト様が詳しいです。

 

実際にやってみた

Eclipseを起動して、適当にJavaプロジェクトを作成。クラスも作成。

そしたらば、今回は、結果をファイルに書き込みたいので、適当にフォルダを作成し、ファイルも作成。(Maven や、Gradle なんかのビルドツールでプロジェクトを作成してる場合は、プロジェクトのフォルダの構成とかも変わってくると思われます。)

f:id:ts0818:20190817115155p:plain

今回、「FunctionIFTest」ってJavaプロジェクトを作成しているので、プロジェクトディレクトリ直下に、「file」というフォルダを作成しました。

f:id:ts0818:20190817115250p:plain

「file」フォルダ直下に、ファイルを作成で。

f:id:ts0818:20190817115511p:plain

適当なファイルを作成で。

f:id:ts0818:20190817115629p:plain

今回は、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();
    }
  }
}

んで、実行してみる。

f:id:ts0818:20190817152404p:plain

f:id:ts0818:20190817152455p:plain

テキストファイルに出力されました。Loggerクラスのインスタンスとか用意しておきながら、使ってないや...

Stream API の limit() が無いと無限ループ?になってしまうようなので、どこまで処理するか制限を設ける必要があるようです。まぁ、このへんは決め打ちで指定するしかないかと。(だって、素数がいくつあるかを調べたいんだから、事前に素数がいくつあるかなんて分かるわけないしね) 

クラス名を、Eratoshenes とかにしちゃったけど、全然、「エラトステネスの篩」になってないっす(涙)。

 

ファイルの2GBの壁に関する問題は、

kazuhira-r.hatenablog.com

⇧  上記サイト様によりますと、java.nio.file.Files パッケージのcopy メソッドなら問題なく回避できるらしいです。

 

ファイルパスとかは、

blog.morugu.com

⇧  上記サイト様を参考にさせていただきました。

 

ちなみに、Stream API ですが、

qiita.com

⇧ 上記サイト様が詳しいです。

発展途上ということで、Java 9 とかでちょこっと機能が追加されてるそうです。 

Stream API の peek() メソッドとかってデバッグ用途だったんすね。forEach() と違って、戻り値を戻せる状態のままで処理してくれるのはありがたいかな。

 

Wikipedia さんによりますと、

素数判定(そすうはんてい)とは、ある自然数 n が素数であるか合成数であるかを判定する問題である。素数判定を行うアルゴリズムのことを素数判定法という。

素数判定 - Wikipedia

⇧  かなり、たくさんのアルゴリズムがあるらしい。ネットとかの情報だと「エラトステネスの篩」が多いかな。何を使えば良いのかサッパリですわ... 

 

まぁ、何て言うか、 いつもながら、モヤモヤ感が半端ない...数学の知識ないと厳しい感じがしてならない...

とりあえず、BigInteger クラスの nextProbablePrime() メソッドは、あんまりイケてないらしいということですかね。

今回はこのへんで。