java – 找到第n个素数

发布时间：2020-12-15 05:00:06 所属栏目：Java 来源：网络整理

导读：我在下面写了下面的代码来找到第n个素数.这可以改善时间复杂度吗？描述： ArrayList arr存储计算的素数.一旦arr达到’n’大小,循环退出,我们检索ArrayList中的第n个元素.在计算素数之前添加数字2和3,并且从4开始的每个数字被检查为素数或不是素数. public v

我在下面写了下面的代码来找到第n个素数.这可以改善时间复杂度吗？

描述：

ArrayList arr存储计算的素数.一旦arr达到’n’大小,循环退出,我们检索ArrayList中的第n个元素.在计算素数之前添加数字2和3,并且从4开始的每个数字被检查为素数或不是素数.

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>(); // stores prime numbers 
                                                      // calculated so far
    // add prime numbers 2 and 3 to prime array 'arr'
    arr.add(2); 
    arr.add(3);

    // check if number is prime starting from 4
    int counter = 4;
     // check if arr's size has reached inp which is 'n',if so terminate while loop
    while(arr.size() <= inp) {
        // dont check for prime if number is divisible by 2
        if(counter % 2 != 0) {
            // check if current number 'counter' is perfectly divisible from 
           // counter/2 to 3
            int temp = counter/2;
            while(temp >=3) {
                if(counter % temp == 0)
                    break;
                temp --;
            }
            if(temp <= 3) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp));
    }
}

解决方法

是.

你的算法进行O(n ^ 2)运算(也许我不准确,但看起来如此),
其中n是结果.

有http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes算法采用O(ipn * log(log(n))).您只能在其中执行inp步骤,并假设n = 2ipn * ln(ipn).
n应该比ipn-prime更大.
(我们知道素数的分布http://en.wikipedia.org/wiki/Prime_number_theorem)

无论如何,您可以改进现有的解决方案：

public void calcPrime(int inp) {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    arr.add(2);
    arr.add(3);

    int counter = 4;

    while(arr.size() < inp) {
        if(counter % 2 != 0 && counter%3 != 0) {
            int temp = 4;
            while(temp*temp <= counter) {
                if(counter % temp == 0)
                    break;
                temp ++;
            }
            if(temp*temp > counter) {
                arr.add(counter);
            }
        }
        counter++;
    }

    System.out.println("finish" +arr.get(inp-1));
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!