最快的算法来查找BigInteger是否为素数？ [英] Fastest algorithm to find if a BigInteger is a prime number or not?

问题描述

我正在编写一种方法来检测BigInteger是否为素数。我使用以下代码/算法来检查给定数字是否为素数。但这是非常缓慢的，如果一个数字可以说长10个数字需要很长时间。

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.

 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中找不到与此相关的问题。如果您遇到过这样的问题请告诉我，或者如果您对如何解决有所了解，那么您的想法将受到高度赞赏。

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.

推荐答案

这是一个优化版本，仅使用最高sqrt（n）测试并使用Miller-Rabin测试（从Joni的答案开始）：

Here's an optimized version using testing only up to sqrt(n) and using the Miller-Rabin test (as of Joni's answer):

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;
}

这篇关于最快的算法来查找BigInteger是否为素数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！