数値がJavaで素数であるかどうかを確認する
1. 序章
まず、いくつかの基本的な理論を見てみましょう。
簡単に言えば、1と数自体で割り切れる場合、数は素数です。 非素数は合成数と呼ばれます。 そして、ナンバーワンは素数でも複合でもありません。
この記事では、Javaの数の素数性をチェックするさまざまな方法を見ていきます。
2. カスタム実装
このアプローチでは、2から(数値の平方根)までの数値が数値を正確に除算できるかどうかを確認できます。
数値が素数の場合、次のロジックはtrueを返します。
public boolean isPrime(int number) {
return number > 1
&& IntStream.rangeClosed(2, (int) Math.sqrt(number))
.noneMatch(n -> (number % n == 0));
}
3. BigIntegerを使用する
BigInteger クラスは、通常、64ビットを超える大きなサイズの整数を格納するために使用されます。 intおよびlong値を操作するためのいくつかの便利なAPIを提供します。
それらのAPIの1つは、isProbablePrimeです。 このAPIは、数値が確実に複合である場合は false を返し、素数である可能性がある場合はtrueを返します。 大きな整数を処理する場合は、これらを完全に検証するために非常に集中的な計算になる可能性があるため、便利です。
簡単な補足– isProbablePrime APIは、「ミラー-ラビンおよびルーカス-レーマー」素数テストと呼ばれるものを使用して、数がおそらく素数であるかどうかを確認します。 数値が100ビット未満の場合は、「ミラー-ラビン」検定のみが使用されます。それ以外の場合は、数値の素数性をチェックするために両方の検定が使用されます。
「ミラーラビン」テストは、数値の素数性を決定するために一定の回数反復し、この反復カウントは、数値のビット長とAPIに渡される確実性の値を含む単純なチェックによって決定されます。 :
public boolean isPrime(int number) {
BigInteger bigInt = BigInteger.valueOf(number);
return bigInt.isProbablePrime(100);
}
4. ApacheCommonsMathの使用
Apache Commons Math APIは、 org.apache.commons.math3.primes.Primes、という名前のメソッドを提供します。このメソッドは、数値の素数性をチェックするために使用します。
まず、 pom.xml に次の依存関係を追加して、ApacheCommonsMathライブラリをインポートする必要があります。
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-math3</artifactId>
<version>3.6.1</version>
</dependency>
commons-math3の最新バージョンは、ここにあります。
メソッドを呼び出すだけでチェックを実行できます。
Primes.isPrime(number);
5. 結論
この簡単な記事では、数の素数性をチェックする3つの方法を見てきました。
このためのコードは、Githubのパッケージ com.baeldung.algorithms.primecheckerにあります。