Javaでの素数の生成

投稿日: 2019-10-18 2022-10-25
タグ: Java

1. 序章

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

数が素数であるかどうかを確認したい場合は、その方法に関するクイックガイドをご覧ください。

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で割り切れるので、素数が偶数になることはありません。

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

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. Java8の使用

Java8イディオムを使用して以前のソリューションを書き直す方法を見てみましょう。

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)))
      .allMatch(n -> x % n != 0);
}

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

素数を効率的に生成するのに役立つさらに別の効率的な方法があり、それはSieveOfEratosthenesと呼ばれます。その時間効率はO（n logn）です。

このアルゴリズムの手順を見てみましょう。

2からnまでの連続する整数のリストを作成します：（2、3、4、…、n）
最初に、 p を2、最初の素数に等しくします。
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でどのように機能するか見てみましょう。

上の画像を考えてみましょう。アルゴリズムによって作成されたパスは次のとおりです。

ループは2で始まるので、2をマークせずに残し、2の約数をすべてマークします。画像に赤い色でマークされています
ループは3に移動するため、3をマークせずに残し、まだマークされていない3の約数をすべてマークします。画像では緑色でマークされています
ループは4に移動し、すでにマークされているので、続行します
ループは5に移動するため、5をマークせずに残し、まだマークされていない5の約数をすべてマークします。画像に紫色でマークされています
ループがnの平方根に等しくなるまで、上記の手順を続けます。

4. 結論

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

これらの例の実装は、GitHubのにあります。

getdocs

13036