找到第n个素数

Question

我在下面写了下面的代码来找到第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));
    }
}

Answer 1

是.

你的算法进行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));
    }
}