我正在写一个方法来检测BigInteger是否是素数。我使用以下代码/算法检查给定数字是否为质数。但这非常慢,如果一个数字可以说是10位数字,则需要很长时间。
public boolean returnPrime(BigInteger testNumber){ int divisorCounter=1; BigInteger index,i ; for ( index= new BigInteger("2"); index.compareTo(testNumber) !=1; index=index.add(new BigInteger("1"))){ System.out.println(index); for(i= new BigInteger("2"); i.compareTo(index) != 1; i=i.add(new BigInteger("1"))){ if((testNumber.mod(i).equals(BigInteger.ZERO) )){ divisorCounter++; } if(divisorCounter>2){ return false; } } } return true; }
有没有更好的算法可以与BigInteger质数一起使用?我在Stackoverflow中找不到与此相关的问题。如果您遇到了这样的问题,请让我知道,或者如果您对解决方法有任何想法,则非常感谢您的想法。
这是一个优化版本,仅使用sqrt(n)进行测试,并使用Miller-Rabin测试(根据Joni的回答):
public boolean returnPrime(BigInteger number) { //check via BigInteger.isProbablePrime(certainty) if (!number.isProbablePrime(5)) return false; //check if even BigInteger two = new BigInteger("2"); if (!two.equals(number) && BigInteger.ZERO.equals(number.mod(two))) return false; //find divisor if any from 3 to 'number' for (BigInteger i = new BigInteger("3"); i.multiply(i).compareTo(number) < 1; i = i.add(two)) { //start from 3, 5, etc. the odd number, and look for a divisor if any if (BigInteger.ZERO.equals(number.mod(i))) //check if 'i' is divisor of 'number' return false; } return true; }