java - 找到并返回第k个元素

从所有素数2、3、5、7、11、13、17、19、23，...的无穷序列中找到并返回第k个元素（从零开始，在计算机科学中通常如此）。可以假设k为非负数。

isPrime可以工作，kthPrime可以编译，但是可以永久运行...不确定如何使它更快

public static boolean isPrime(int n){
    if (n<2) return false;
    for (int i=2;i<=Math.sqrt(n);i++){
        if (n%i==0)
          return false;
    }
    return true;
}

public static int kthPrime(int k){
    int counter=0;
    for (int i=0;i<=Integer.MAX_VALUE;i++){
        if (isPrime(i)){
            counter++;
            if(counter==k)
                return i;
        }
    }
    return -1;
}

单元测试：

@Test public void kthPrimeTest() {
    CRC32 check = new CRC32();
    for(int k = 0; k < 30_000; k++) {
        check.update(Primes.kthPrime(k));
    }
    assertEquals(3080752681L, check.getValue());
}

最佳答案

您的问题是在k = 0上运行时的情况。

在方法开始时将其添加到您的kthPrime代码中：

if (k == 0) {
    return 2;
}

这将添加一个检查，如果k是0，则它将不会永远运行。

看到这个块：

if (isPrime(i)){
   counter++;
   if(counter==k)
       return i;
}

在这里，您可以看到当k为0时，计数器将增加为1，从而使counter == k成为1 == 0，这永远是不正确的，因此代码只有在命中Integer.MAX_VALUE时才会退出，这将需要很长时间。