在 java 中以低时间复杂度找到第 n 个素数

Question

我正在尝试找到一个低时间复杂度的解决方案来寻找第 n 个素数。但是有一些方法问题我很困惑。另外我想知道我的时间复杂度是低还是可以更好？

我尝试了两种不同的方法来找到质数，但第一种太慢了，所以我换了另一种。但是布尔方法有一些我不知道的问题。

public static int FInd_NthPrime(int n){
        int num=0,j,c=2;
        while (true) {
            if(isPrime(c)){
                num = num+1;
            }
            c = c+1;
            break;
        }
        return c; // the error happened
}

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


public static void print_nth_prime(int num){
    int result = FInd_NthPrime(num);
    System.out.print(num +" "+result);
}

我希望有人告诉我布尔方法的错误，有没有更好的方法来降低寻找第 n 个素数的时间复杂度。

Answer 1

您只需测试奇数和特殊情况“2”。

并且在进行 isPrime 测试时，只需对已经发现的现有素数进行取模检查。

public static int FInd_NthPrime(int n){

    int val = 3;    // first odd number greater than 2
    int result = 0;

    if (n <= 1) {
        return 2;  // special case for 2, the only even prime
    }

    // build up a Hash table of all discovered primes so far
    ArrayList<Integer> primes = new ArrayList<Integer>();
    primes.add(2);

    while (n > 1) {
        if (isPrime(val, primes)) {
            n--;
            result = val;
        }
        val += 2;  // increment to the next odd integer
    }
    return result;
}

public static boolean isPrime(int n, ArrayList<Integer> primes) {

    if (n == 2) {
        return true;
    }

    int stop = (int)Math.sqrt(n);

    for (int divisor : primes) {
        if ((n % divisor) == 0)  {
            return false;
        }
        if (divisor > stop) {
            break;
        }
    }

    //System.out.format("Added %d to prime list\n", n);
    primes.add(n);
    return true;
}

在 java 中以低时间复杂度找到第 n 个素数

find nth prime in java with low time complexity

java

primes