Use nextprobableprime () for java to get previousprobableprime

Question

I want to use the nextProbablePrime() BigInteger method to get a prime number that is less than a given number, not higher.

Is it possible to get it using only one nextProbablePrime call?

Answer 1

I do not know if the nextProbablePrime method can be used (in one call). However, I just need the previousProbablePrime method, and I came up with the following method that uses the isProbablePrime method in the 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; } 

I installed the following test to compare speed (and accuracy) with the nextProbablePrime method:

 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); } 

The Stopwatch class is just a basic custom class for tracking runtime, so change these parts to fit the class you may have for this.

I tested the ranges from 1 to 10000, 100000 and 1000000. The previousProbablePrime method took more time to execute in all three tests. However, it turned out that the difference in execution time increased only modestly with each increase in the size of the range by 10 times. For 10000, previousProbablePrime takes a little less than a second, and nextProbablePrime about 200 ms, for a difference of about 700 or 800 ms. For 1,000,000, the difference was only about 2 seconds, although the runtime was 9 and 7 seconds, respectively. Conclusion, the difference in execution time increases more slowly than the size of the range.

In all tests, the two lists contained the same set of primes.

This level of efficiency was sufficient for my needs ... might work for you too.