java 查找 BigInteger 是否为素数的最快算法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/32035259/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fastest algorithm to find if a BigInteger is a prime number or not?
提问by Ram
I am writing a method that detects if a BigInteger is prime or not. I have used the following code/algorithm to check if a given number is prime or not. But this is extremely slow and takes long time if a number is lets say 10 digits long.
我正在编写一种检测 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;
}
Is there any better algorithms to work with BigInteger prime number? I could not find a question related to this in Stackoverflow. If you have came across such question please let me know or if you have an idea on how to solve then your ideas are much appreciated.
有没有更好的算法来处理 BigInteger 素数？我在 Stackoverflow 中找不到与此相关的问题。如果您遇到过这样的问题，请告诉我，或者如果您对如何解决有任何想法，那么非常感谢您的想法。
回答by Juan Lopes
Here's an optimized version using testing only up to sqrt(n) and using the Miller-Rabin test (as of Joni's 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;
}
回答by Joni
Check if the integer is a "probable prime." If it's not you know for sure that it's composite and you avoid the slow factorization.
检查整数是否是“可能的素数”。如果不是，您肯定知道它是复合的，并且避免了缓慢的因式分解。
if (!testNumber.isProbablePrime(5)) return false;
Also you only need to make trial divisions only up to the square root of testNumber. If K is composite you know that its least prime factor must be at most sqrt(K).
此外，您只需将试除法划分为 的平方根testNumber。如果 K 是复合的，你知道它的最小素因子最多是 sqrt(K)。
回答by Brendan Rollinson
Some other simple improvements would be to limit your set of possible numbers to only two and odd numbers in your outer loop and also to only iterate up to the square root of "index" (or index / 2 if too hard to calculate) in your inner loop.
其他一些简单的改进是将您的可能数字集限制为外循环中只有两个和奇数，并且仅迭代到您的“索引”（或索引 / 2，如果太难计算）的平方根内循环。
