1前書き

このチュートリアルでは、Javaを使用して素数を生成するためのさまざまな方法を紹介します。

数字が素数であるかどうかを確認する場合は、こちらのリンクを参照してください。/java-prime-numbers


2素数

コアの定義から始めましょう。素数とは、1以上の自然数で、1以上の正の約数はありません。

たとえば、1と7が唯一の正の整数因子であるため7は素数ですが、12は1、4、6に加えて約数3と2があるからではありません。


3素数の生成

このセクションでは、与えられた値よりも小さい素数を効率的に生成する方法を説明します。


3.1. Java 7以前 – 総当たり

public static List<Integer> primeNumbersBruteForce(int n) {
    List<Integer> primeNumbers = new LinkedList<>();
    for (int i = 2; i <= n; i++) {
        if (isPrimeBruteForce(i)) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}
public static boolean isPrimeBruteForce(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

ご覧のとおり、

primeNumbersBruteForce

は2から

n

までの数字を繰り返し処理し、

isPrimeBruteForce()

メソッドを呼び出して数字が素数かどうかを確認しています。

このメソッドは、2から

number-1

までの範囲の数で各数の可分性を調べます。

  • ある数で割り切れる数に遭遇した場合は、falseを返します** その数がその前の数のいずれかで割り切れないことがわかったときに、その整数を示すtrueを返します。


3.2. 効率と最適化

前のアルゴリズムは線形ではなく、時間の複雑さはO(n ^ 2)です。このアルゴリズムも効率的ではなく、明らかに改善の余地があります。


isPrimeBruteForce()

メソッドの中の条件を見てみましょう。

数が素数でない場合、この数は2つの要素、すなわち

a



b

、すなわち

number

= a

bに因数分解できます。


a



b

の両方が

n

の平方根より大きい場合、

a ** b



n

より大きくなります。

そのため、これらの因子の少なくとも1つは数値の平方根以下でなければならず、数値が素数であるかどうかを確認するには、確認する数値の平方根以下の因子をテストするだけで済みます。

偶数は2で割り切れるので、素数は偶数になることはありません。

さらに、偶数は2で割り切れるので、素数は偶数になることはありません。

上記のアイデアを念頭に置いて、アルゴリズムを改良しましょう。

public static List<Integer> primeNumbersBruteForce(int n) {
    List<Integer> primeNumbers = new LinkedList<>();
    if (n >= 2) {
        primeNumbers.add(2);
    }
    for (int i = 3; i <= n; i += 2) {
        if (isPrimeBruteForce(i)) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}
private static boolean isPrimeBruteForce(int number) {
    for (int i = 2; i** i < number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}


3.3. Java 8

を使用する

Java 8のイディオムを使用して以前のソリューションを書き換える方法を見てみましょう。

public static List<Integer> primeNumbersTill(int n) {
    return IntStream.rangeClosed(2, n)
      .filter(x -> isPrime(x)).boxed()
      .collect(Collectors.toList());
}
private static boolean isPrime(int number) {
    return IntStream.rangeClosed(2, (int) (Math.sqrt(number)))
      .filter(n -> (n & 0X1) != 0)
      .allMatch(n -> x % n != 0);
}


3.4. エラトステネスのふるいの使用

素数を効率的に生成するのに役立つもう1つの効率的な方法があります。それはSieve Of Eratosthenesと呼ばれます。その時間効率はO(n logn)です。

このアルゴリズムのステップを見てみましょう。

  1. 2から

    n

    までの連続した整数のリストを作成します. (2、3、4、…​、n)

  2. 最初に、

    p

    を2、最初の素数と等しくします


  3. p

    から始めて、

    p

    の増分でカウントアップし、それぞれにマークを付けます.

これらの数は、リスト内の

p

よりも大きくなっています。これらの数はなります
2p、3p、4pなど。それらのいくつかは既にマークされているかもしれないことに注意してください
。マークされていないリストで、

p

よりも大きい最初の番号を見つけます。

そのような数がなかったら、やめなさい。それ以外の場合は、

p

をこの数(次の素数)に等しくし、手順3から繰り返します。

アルゴリズムが終了する最後に、マークされていないリスト内のすべての数は素数です。

コードは次のようになります。

public static List<Integer> sieveOfEratosthenes(int n) {
    boolean prime[]= new boolean[n + 1];
    Arrays.fill(prime, true);
    for (int p = 2; p **  p <= n; p++) {
        if (prime[p]) {
            for (int i = p **  2; i <= n; i += p) {
                prime[i]= false;
            }
        }
    }
    List<Integer> primeNumbers = new LinkedList<>();
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}


3.5. エラトステネスのふるいの使用例

n = 30の場合の動作を見てみましょう。


/uploads/Primes.jpg

+

+

+上の画像を見てください、ここでアルゴリズムによって行われたパスです:

  1. ループは2から始まるので、2をマークしないままにし、すべてをマークします.

2の約数。イメージ内では赤い色でマークされています
。ループは3に移動するので、3をマークせずにすべての約数をマークします。

3のうちまだマークされていません。画像には緑色で表示されています
。ループは4に移動し、すでにマークされています。

  1. ループは5に移動するので、5をマークせずに5のすべての約数をマークします.

まだマークされていません。画像には紫色のマークが付けられています
。ループがの平方根に等しくなるまで上記のステップを続けます


n


4結論

このクイックチュートリアルでは、N値まで素数を生成する方法を説明しました。

これらの例の実装はhttps://github.com/eugenp/tutorials/tree/master/java-numbers[GitHubに追加]を参照してください。