найти n-е простое число в Java с низкой сложностью времени - PullRequest
Новая
       55

найти n-е простое число в Java с низкой сложностью времени

0 голосов
/ 20 сентября 2019

Я пытаюсь найти решение с малой временной сложностью для поиска 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-го простого числа。

1 Ответ

1 голос
/ 20 сентября 2019

Вам нужно только проверить нечетные целые числа и особый случай "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;
}
...