java - 为什么它不终止 - BigInteger Prime 测试

Question

我写了两个方法来测试 BigInteger 是否是质数。我从 (2^64)+1 开始，然后我总是加 2 直到找到素数。这是两种方法:

public static boolean isPrime(BigInteger n) {

    BigInteger max_long = BigInteger.valueOf(Long.MAX_VALUE);       
    if (n.compareTo(max_long)<=0) return isPrime(n.longValue());

    final BigInteger two = new BigInteger ("2");

    if ((n.mod(two)).compareTo(BigInteger.ZERO)==0) return false;

    else {
        for (BigInteger i=new BigInteger ("3"); i.multiply(i).compareTo(n)<=0; i=i.add(two)) {
            if((n.mod(i)).compareTo(BigInteger.ZERO)==0) return false;
        }
    }
    return true;
}

另一个是:

public static boolean isPrimeImproved (BigInteger n) {
    BigInteger max_long = BigInteger.valueOf(Long.MAX_VALUE);
    if(n.compareTo(max_long)<=0) return isPrime(n.longValue());

    final BigInteger two = new BigInteger("2");
    if(n.mod(two).compareTo(BigInteger.ZERO)==0) return false;

    else {
        for(BigInteger i=new BigInteger("3"); i.multiply(i).compareTo(n)<=0; i=i.nextProbablePrime()) {
             if(n.mod(i).compareTo(BigInteger.ZERO)==0) return false;
        }       
    }
    return true;

}

第一个在大约 310 秒后终止。但是第二个似乎并没有终止，虽然它应该更快，不是吗？我知道，有一个名为 isProbablePrime() 的方法，但我不能使用它。

Answer 1

你的for循环需要 BigInteger每次循环乘法:i.multiply(i).compareTo(n)<=0;鉴于我们在 Long.MAX_VALUE 以上工作那么这是一个很多昂贵的乘法。执行单个平方根计算以找到循环的固定限制可能会更快:i.compareTo(iSqrt)<=0;

编写一段简单的 Newton-Raphson 代码来求整数平方根非常容易。它只会运行一次，并将取代许多昂贵的乘法。 Crandall 和 Pomerance 提供了一个版本，我相信还有其他版本。