小编典典

查找BigInteger是否为质数的最快算法?

algorithm

我正在写一个方法来检测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中找不到与此相关的问题。如果您遇到了这样的问题,请让我知道,或者如果您对解决方法有任何想法,则非常感谢您的想法。


阅读 446

收藏
2020-07-28

共1个答案

小编典典

这是一个优化版本,仅使用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;
}
2020-07-28