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))

Answer 2

Конечно! Вот пример кода на языке Python 3, который решает задачу:

pythonCopy code
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def find_nth_prime(n):
    count = 0
    number = 2
    while count < n:
        if is_prime(number):
            count += 1
        number += 1
    return number - 1

# Чтение входных данных из файла
with open('input.txt', 'r') as file:
    k = int(file.readline())

# Поиск K-го простого числа
result = find_nth_prime(k)

# Запись результата в выходной файл
with open('output.txt', 'w') as file:
    file.write(str(result))

В этом примере используется функция is_prime(), которая проверяет, является ли число простым. Затем функция find_nth_prime() используется для поиска K-го простого числа. Входные данные считываются из файла input.txt, а результат записывается в файл output.txt.

Обратите внимание, что файлы input.txt и output.txt должны находиться в той же папке, где находится скрипт.