Javaで素数を決める方法

投稿日: 2019-11-05 2019-11-05
タグ: Java, prime number

数学とセキュリティの非常に重要な質問は、数字が素数かどうかを調べることです。これは、パスワードを暗号化するときに非常に便利です。このチュートリアルでは、単純な場合に数値が素数であるかどうかを調べる方法を学習します。

簡単なケース

彼らが持っている唯一の除数が1であれば、数は素数であることがわかりました。簡単には、1からそれ自身（排他的）までのすべての整数をチェックし、均等に分割するかどうかをテストできます。

たとえば、次のアルゴリズムを実行することができます。

….//checks whether an int is prime or not.
boolean isPrime(int n) {
for(int i=2;i<n;i++) {
if(n%i==0)
return false;
}
return true;
}

これは最初は悪くはないように見えますが、速度を上げることができます。

2が整数nをいくつか除算すると、（n/2）もnを除算することを考慮してください。

これは、2からnまでのすべての整数を試す必要がないことを示しています。今度はアルゴリズムを変更できます:

....//checks whether an int is prime or not.
boolean isPrime(int n) {
    for(int i=2;2** i<n;i++) {
        if(n%i==0)
            return false;
    }
    return true;
}

より効率的なコーディングでは、実際にnの平方根に行く必要があることに気づきます。数字のすべての要素を列挙すると、平方根は常に中間になります整数でなくてもOKですが、あまりにも近似するかもしれませんが、コードはまだ動作します）。

最後に、我々は2が “奇妙な”素数であることを知っています – それは唯一の素数であることがあります。このため、2つを別々にチェックするだけで、nの平方根まで奇数をトラバースする必要があります。結局、私たちのコードは次のようになります:

….//checks whether an int is prime or not.
boolean isPrime(int n) {
//check if n is a multiple of 2
if (n%2==0) return false;
//if not, then just check the odds
for(int i=3;i** i⇐n;i+=2) {
if(n%i==0)
return false;
}
return true;
}

分かるように、整数の半分を平方根（実際には奇数のもの）までチェックするだけで、あらゆる整数（nが素数であることを知るためにnまで）をチェックしています。これは大きな数字です。

=== 繰り返し

多くの数字が素数であるかどうかを確認するように求められるプログラムを書くとしましょう。一度だけではありません。上記のプログラムはそのアルゴリズムに高度に最適化されていますが、この状況に特に適した別の方法があります:Prime Sieve。

基本的な考え方は次のとおりです。

.  2以上のすべての整数が素数であると仮定します.

. リストの先頭から開始し、数字が素数ならば、クロスアウトする

その数の倍数をリストから外します。彼らはプライムではありません。

. 次の番号に移動し、それが外れている場合はスキップします. そうではありません

プライム。それが外に出ていなければ、それは素数でなければならず、それは倍数になります。

. 繰り返す

これが何を意味するか見てみましょう。リストを考えてみましょう:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 …

2は素数です...それは倍数です。私たちのリストは次のようになります:
**  2 3 4 5[ラインスルー]**  6 **  7[ラインスルー]**  8 **  9[ラインスルー]**  10 **  11[ラインスルー]**  12 **  13[ラインスルー]**  14 **  15[ラインスルー]**  16 **  17

[line-through]** 18**  19[line-through]** 20**  ...**

あなたはなぜ2が唯一の素数であるかを見ることができます。今度は3でそれをすると、6（すでにクロスアウト）、9,12（すでにクロスアウト）、15など

結局あなたのリストは次のようになります:
**  2 3 4 5[ラインスルー]**  6 **  7[ラインスルー]**  8 ** [ラインスルー]**  9 ** [ラインスルー]**  10 **  11[ラインスルー]**  12 **  13[ラインスルー]**  14 **

[line-through]** 15** [line-through]** 16**  17[line-through]** 18**  19

[line-through]** 20**  ...**

そして、私たちの素数は残ったものです:（2,3,5,7,11,13,17,19,23,29、...）。

コードでは、このリストを配列として追跡することができます。つまり、この「ふるい」を設定するにはn個の数字を使いますが、数字が素数であるかどうかにかかわらず瞬間的な値を返すので、関数を繰り返し呼び出すときに補うことになります。ここにそれはどのように見えるのですか。もちろん、自分のニーズに合わせてこれを編集することもできます:

import java.util.Arrays;//global array just to keep track of it in this example, //but you can easily do this within another function.
boolean[]primes=new boolean[10000]; //set up the primesieve
public void fillSieve() {
Arrays.fill(primes,true); //assume all integers are prime.
primes[0]=primes[1]=false; //we know 0 and 1 are not prime.
for (int i=2;i<primes.length;i) {
//if the number is prime,
//then go through all its multiples and make their values false.
if(primes[i]) {
for (int j=2;i** j<primes.length;j) {
primes[i** j]=false;
}
}
}
}

public boolean isPrime(int n) {
return primes[n];//simple, huh?
}

リンク://タグ/java/[java]link://タグ/素数/素数

getdocs

13036