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

import timeit
import cProfile

era = """
def eratosthenes(index):
    n = 16000
    sieve = [i for i in range(n)]
    sieve[1] = 0

    for i in range(2, n):
        if sieve[i] != 0:
            j = i + i
            while j < n:
                sieve[j] = 0
                j += i

    res = [i for i in sieve if i != 0]
    return res[index]

eratosthenes(1)
"""

# В моем исполнении этих функций не имеет особого значения какой индекс я хочу найти т.к. при возврате
# значения используется срез, который создет копию всего массива. Из-за этого я буду изменять длину массива (n)

# number = 1000
# 1000 0.25614109999999995
# 2000 0.5483457
# 4000 1.0652346000000001
# 8000 2.7806614
# 16000 5.609768

# График функции линеен


second = """
def second_var(index, n=1000):
    lst = []
    if len(lst) < index:
        for i in range(2, n+1):
            for j in range(2, i):
                if i % j == 0:
                    break
            else:
                lst.append(i)

    return lst[index]

second_var(1, n=8000)
"""
# number=1000
# 1000 3.4264235
# 2000 12.8650159
# 4000 49.144664
# 8000 211.22408130000002 (тут я пошел пить кофе)
# 16000 ---   (а здесь уже не рисковал)


# Второй вариант однозначно лучше. Конечно, это из-за времени выполнения.





