java - java の nextprobableprime() を使用して、previousprobableprime を取得します。

Question

nextProbablePrime()のメソッドを使用BigIntegerして、指定された数値よりも大きい素数ではなく小さい素数を取得したいと考えています。

1回の電話で取得できnextProbablePrimeますか？

Answer 1

nextProbablePrimeメソッドを（1回の呼び出しで）使用できるかどうかはわかりません。ただし、メソッドが必要だったので、APIでpreviousProbablePrimeメソッドを使用する次のメソッドを思いつきました。isProbablePrimeBigInteger

public static BigInteger previousProbablePrime(BigInteger val) {
    // To achieve the same degree of certainty as the nextProbablePrime 
    // method, use x = 100 --> 2^(-100) == (0.5)^100.
    int certainty = 100;
    do {
        val = val.subtract(BigInteger.ONE);
    } while (!val.isProbablePrime(certainty));
    return val;
}

nextProbablePrime速度 (および精度) をメソッドと比較するためだけに、次のテストを設定しました。

private static void testPreviousProbablePrime() {
    BigInteger min = BigInteger.ONE; // exclusive
    BigInteger max = BigInteger.valueOf(1000000); // exclusive
    BigInteger val;

    // Create a list of prime numbers in the range given by min and max 
    // using previousProbablePrime method.
    ArrayList<BigInteger> listPrev = new ArrayList<BigInteger>();
    Stopwatch sw = new Stopwatch();
    sw.start();

    val = BigIntegerUtils.previousProbablePrime(max);
    while (val.compareTo(min) > 0) {
        listPrev.add(val);
        val = BigIntegerUtils.previousProbablePrime(val);
    }
    sw.stop();
    System.out.println("listPrev = " + listPrev.toString());
    System.out.println("number of items in list = " + listPrev.size());
    System.out.println("previousProbablePrime time = " + sw.getHrMinSecMsElapsed());

    System.out.println();

    // Create a list of prime numbers in the range given by min and max 
    // using nextProbablePrime method.
    ArrayList<BigInteger> listNext = new ArrayList<BigInteger>();
    sw.reset();
    sw.start();

    val = min.nextProbablePrime();
    while (val.compareTo(max) < 0) {
        listNext.add(val);
        val = val.nextProbablePrime();
    }
    sw.stop();
    System.out.println("listNext = " + listNext.toString());
    System.out.println("number of items in list = " + listNext.size());
    System.out.println("nextProbablePrime time = " + sw.getHrMinSecMsElapsed());

    System.out.println();

    // Compare the two lists.
    boolean identical = true;
    int lastIndex = listPrev.size() - 1;
    for (int i = 0; i <= lastIndex; i++) {
        int j = lastIndex - i;
        if (listPrev.get(j).compareTo(listNext.get(i)) != 0) {
            identical = false;
            break;
        }
    }
    System.out.println("Lists are identical?  " + identical);
}

このStopwatchクラスは、実行時間を追跡するための基本的なカスタム クラスにすぎないため、これらの部分を変更して、このために使用する可能性のあるクラスに合わせます。

1 から 10000、100000、および 1000000 の範囲をテストしましたpreviousProbablePrime。3 つのテストすべてで、メソッドの実行に時間がかかりました。ただし、実行時間の差は、範囲サイズが 10 倍になるごとにわずかにしか増加しないように見えました。10000 の場合、previousProbablePrime1 秒弱で実行されましたnextProbablePrimeが、約 200 ミリ秒で実行され、約 700 または 800 ミリ秒の差がありました。1000000 の場合、実行時間はそれぞれ 9 秒と 7 秒でしたが、その差は約 2 秒でした。結論として、実行時間の差は、範囲サイズよりもゆっくりと増加します。

すべてのテストで、2 つのリストには同じ素数のセットが含まれていました。

このレベルの効率は、私のニーズには十分でした...あなたにも役立つかもしれません.

私はテストしていませんが、編集メソッドの実装をより効率的で潜在的に高速になるように変更しました。

public static BigInteger previousProbablePrime(BigInteger val) {
    if (val.compareTo(BigInteger.TWO) < 0) {
        throw new IllegalArgumentException("Value must be greater than 1.");
    }

    // Handle single unique case where even prime is returned.
    if (val.equals(new BigInteger("3"))) {
        return BigInteger.TWO;
    }

    // To achieve the same degree of certainty as the nextProbablePrime 
    // method, use x = 100 --> 2^(-100) == (0.5)^100.
    int certainty = 100;

    boolean isEven = val.mod(BigInteger.TWO).equals(BigInteger.ZERO);

    val = isEven ? val.subtract(BigInteger.ONE) : val.subtract(BigInteger.TWO);

    while (!val.isProbablePrime(certainty)) {
        // At this point, only check odd numbers.
        val = val.subtract(BigInteger.TWO);
    }

    return val;
}