Question

Язык Python3

Простое число
По введённому натуральному числу K, не превосходящему 100000, выдать K-е по счёту простое число.

Входные данные

Во входном файле находится одно натуральное число K.

Выходные данные

В выходной файл выведите K-е простое число.

Примеры

Ввод:
3
Вывод:
5
Ввод:
1
Вывод:
2


Помогите, пожалуйста

Answer 1

Примечание:

Использовался ЯП Python3. Версия: 3.7.3

Скрины исходного кода и примера прикреплены.

Максимальное время работы программы - не более 8 сек при k=100000.

Объяснение:

Алгоритм основан на решете Эратосфена. Мы создаем таблицу до максимального простого числа (простое число номер 100000 это 1299709

). Затем проверяя числа на простоту с помощью перебора делителей, мы исключаем все числа кратные найденным простым.

Исходный код:

def is_prime(n):

   for i in range(2, int(n ** 0.5) + 1):

       if n % i == 0:

           return False

   return True

def prime(k):

   MAX_PRIME = 1299709

   table = list(range(MAX_PRIME, 1, -2)) + [2]

   skip = set()

   count = 0

   while count != k:

       current = table.pop()

       if current in skip:

           continue

       if is_prime(current):

           count += 1

           skip |= set(range(current*2, MAX_PRIME, current))

   return current

k = int(input())

print(prime(k))