Эффективный алгоритм нахождения k-того простого числа?

Question

[alex_643]

Здравствуйте! Мне нужен эффективный алгоритм нахождения k-того простого числа на питоне. Я пробовал ставить счетчик, но получается большая вычислительная сложность. Если есть реализация с решетом эрастофена то дайте пожалуйста её. Помогите пожалуйста!

def IsPrime(n):
    d = 2
    while d * d <= n and n % d != 0:
        d += 1
    return d * d > n
check = False
n = int(input())
i = 1
s = 0
numbers = []
while s < n:
    i += 1
    if IsPrime(i):
        numbers.append(i)
        s += 1
    else:
        continue
print(numbers[n - 1])

Comments

[hint000]

Должен предупредить: нобелевской премии по математике не бывает, к сожалению.

Answer 1

[Алан Гибизов]

Помощь идёт

Comments

[alex_643]

У меня есть алгоритм, но я не знаю как его применить под мою ситуацию. Ведь мне нужно найти определенное по счету простое число, а в алгоритме нужно число до которого будут находится простые числа.

[Алан Гибизов]

Ну... ставим в качестве целевого числа 10 ** 100, складываем полученные в simple_numbers = [] и ищем while len(simple_numbers) < N.
Вот это гляньте, если еще не видели. Мне понравилось.