# Написать два алгоритма нахождения i-го по счёту простого числа. Функция нахождения простого числа должна принимать на
# вход натуральное и возвращать соответствующее простое число. Проанализировать скорость и сложность алгоритмов.

# Первый - с помощью алгоритма «Решето Эратосфена».
# Примечание. Алгоритм «Решето Эратосфена» разбирался на одном из прошлых уроков. Используйте этот код и попробуйте
# его улучшить/оптимизировать под задачу.

# Второй - без использования «Решета Эратосфена».
# Примечание. Вспомните классический способ проверки числа на простоту.


def hw_4_2_v1(x):
    # x = abs(int(input('Введите натуральное число: '))) # не забудь убрать x в функции
    era = list(range(x + 1))
    era[1] = 0
    for i in era:
        if i > 1:
            for j in range(i + i, len(era), i):
                era[j] = 0
    return era


# print(hw_4_2_v1())


def hw_4_2_v2(y):
    # y = abs(int(input('Введите натуральное число: ')))  # не забудь убрать y в функции
    classic = []
    for i in range(2, y):
        result = True
        for j in range(2, i):
            if i % j == 0:
                result = False
        if result:
            classic.append(i)
    return classic


# print(hw_4_2_v2())


