Язык Python3
Простое число
По введённому натуральному числу K, не превосходящему 100000, выдать K-е по счёту простое число.
Входные данные
Во входном файле находится одно натуральное число K.
Выходные данные
В выходной файл выведите K-е простое число.
Примеры
Ввод:
3
Вывод:
5
Ввод:
1
Вывод:
2
Помогите, пожалуйста
Answers & Comments
Примечание:
Использовался ЯП 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))