java为什么不终止BigInteger素数测试

Question

我写了两个方法来测试一个大整数是否是素数。我从（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;

编写一段简单的牛顿-拉斐逊代码来求整数平方根是很容易的。它将只运行一次，并将取代大量昂贵的乘法运算。Crandall和Pomerance给出了一个版本，我相信还有其他版本