使用java的nextprobableprime（）獲得previousprobableprime

Question

我想要使用nextProbablePrime()方法BigInteger來獲得低於給定數量的素數而不是更高。

是否有可能只使用一個nextProbablePrime調用？

Answer 1

我不知道是否可以使用nextProbablePrime方法（在一次調用中）。但是，我不得不需要一個previousProbablePrime方法，我想出了一個使用isProbablePrime方法BigInteger API在下面的方法：

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方法執行時間更長。然而，似乎執行時間的差異只有在範圍大小每增加10倍時才適度增加。對於10000，previousProbablePrime在不到一秒的時間內執行，而nextProbablePrime進來的時間約爲200毫秒，相差約700或800毫秒。對於1000000，即使執行時間分別爲9秒和7秒，差異也只有2秒左右。結論是，執行時間的差異比範圍大小增加得慢。

在所有測試中，這兩個列表包含相同的一組素數。

這樣的效率水平足以滿足我的需求......也許也適合您。