java - 找到第 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-素数。(我们知道素数的分布 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));
    }
}