无法生成大素数

Question

我正在尝试用Java生成大的素数.我使用BigIntegers.这是我在数组中生成和存储10个素数的代码.

    public static void primeGenerator() {
    BigInteger[] primeList = new BigInteger[10];
    BigInteger startLine = new BigInteger("10");
    int startPower = 6;
    BigInteger endLine = new BigInteger("10");
    int endPower = 9;
    int j = 0;
    for (BigInteger i = fastExp(startLine,startPower); 
            i.compareTo(fastExp(endLine,endPower)) <= 0; 
            i = i.add(BigInteger.ONE)) {
        if (checkPrimeFermat(i) == true && j < 10) {
            primeList[j] = i;
            j++;
        }
    }

    System.out.println(primeList[0]);
    System.out.println(primeList[1]);
    System.out.println(primeList[2]);
    System.out.println(primeList[3]);
    System.out.println(primeList[4]);
    System.out.println(primeList[5]);
    System.out.println(primeList[6]);
    System.out.println(primeList[7]);
    System.out.println(primeList[8]);
    System.out.println(primeList[9]);


}

我编写了自己的fastExp函数来更快地生成数字.这是我的其他功能.

public static BigInteger getRandomFermatBase(BigInteger n)
    {
        Random rand = new Random();

        while (true)
        {
            BigInteger a = new BigInteger (n.bitLength(), rand);

            if (BigInteger.ONE.compareTo(a) <= 0 && a.compareTo(n) < 0)
            {
                return a;
            }
        }
    }

    public static boolean checkPrimeFermat(BigInteger n)
    {
        if (n.equals(BigInteger.ONE))
            return false;

        for (int i = 0; i < 10; i++)
        {
            BigInteger a = getRandomFermatBase(n);
            a = a.modPow(n.subtract(BigInteger.ONE), n);

            if (!a.equals(BigInteger.ONE))
                return false;
        }

        return true;
    }
    public static void main(String[] args) throws IOException 
    {
        primeGenerator();



        }

       public static BigInteger fastExp (BigInteger x, int n){
            BigInteger result=x;
            int pow2=powof2leN(n);
            int residue= n-pow2;
            for(int i=1; i<pow2 ; i=i*2){
                result=result.multiply(result);
                }
            for(int i=0 ; i<residue; i++){
                result=result.multiply(x);          
            }
            return result;

        }

        private static int powof2leN(int n) {
            for(int i=1; i<=n; i=i*2){
                if(i*2>2)
                    return 1;
            }
            return 0;
        }    

}

所以问题是当我尝试使用小数字(例如startPower = 3,endPower = 5)时,它会生成并打印素数.但是,当我尝试使用大数字(例如startPower = 5,endPower = 7)时,它不会生成任何内容.如何改进我的代码以使用大数字？

谢谢

Answer 1

首先,我想指出你没有写这段代码.你从这里偷了它并声称你写了它,这是非常不道德的.

代码是正确的.这很慢.随着功率的增加,代码需要越来越长的时间.出现这种情况有两个原因:

1. 应用Fermat测试的时间越来越长.
2. BigInteger操作需要越来越长的时间来执行.

费马测试像O一样增长(k×log2n×log log n×log log log n).BigInteger的加法和减法像O(n)一样增长.显然,BigInteger正在减缓你的速度.

下面是代码的配置文件,其功率设置为5到7.

如果您希望代码生成越来越大的素数,您应该专注于减少在BigIntegers上执行的操作数量.这是一个这样的改进:

• 走出n.subtract(BigInteger.ONE)你的for循环.结果不需要多次计算.

进一步的建议必须来自数学堆栈交换的数学人员.