最快的算法来判断一个大整数是否为质数？

Question

最快的算法来判断一个大整数是否为质数？

8

我正在编写一个检测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上找不到相关问题。如果你遇到过这样的问题，请告诉我，或者如果你有解决办法，欢迎分享你的想法。

- Ram

1

在2之后，你只需要检查奇数。同时，在达到sqrt(n)后，你可以停止。 - Peter Lawrey

那么在第二个循环之前检查数字是否为质数并将其传递到第二个循环？这听起来不错，可以减少开销，因为我会消除所有偶数。 - Ram

1

而且 sqrt(n) 远小于 n。 - Peter Lawrey

3个回答

5

检查整数是否为“可能的质数”。如果不是，您可以确定它是复合数，并避免缓慢的分解。

if (!testNumber.isProbablePrime(5)) return false;

此外，您只需要对testNumber进行试除法，直到其平方根。如果K是合数，则其最小质因数必须小于或等于sqrt(K)。

- Joni

还有确定性的Miller-Rabin测试变体，适用于给定范围内的数字。链接 - Niklas B.

为什么是 5？这不是很确定。 - Jason S

2

"P < 0.05？让我们发布吧！" :P - Joni

0

一些其他简单的改进是将可能的数字集限制为仅包含两个和奇数数字，在外部循环中，并且在内部循环中仅迭代到“index”的平方根（如果计算太困难，则为index / 2）。

- Brendan Rollinson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Juan Lopes · Accepted Answer

这里是使用最优化的方法，只测试到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;
}