"""Написать два алгоритма нахождения i-го по счёту простого числа.
Без использования «Решета Эратосфена»;
Используя алгоритм «Решето Эратосфена»
Примечание ко всему домашнему заданию: Проанализировать скорость и сложность
 алгоритмов. Результаты анализа сохранить в виде комментариев в файле с кодом."""

from timeit import Timer


def prime(num):
    i = 1
    massive = [2]
    while len(massive) < num:
        i += 2
        massive.append(i)
        for el in massive[0:-1]:
            if i % el == 0:
                massive.pop(-1)
                break
    return f'{num} по счету простое число: {massive[-1]}'
# prime(num=int(input('Введите порядковый номер желаемого простого числа: ')))


def prime_erato(num):
    mass = [i for i in range(100000)]
    mass[1] = 0
    for el in mass:
        if el > 1:
            for j in range(el * 2, len(mass), el):
                mass[j] = 0
    massive = [e for e in mass if e != 0]
    return f'{num} по счету простое число: {massive[num - 1]}'


test_1 = Timer("prime(100)", "from __main__ import prime")
print(prime(100))
print(f"Поиск сотого простого числа: {test_1.timeit(number=500)}")
test_2 = Timer("prime(1000)", "from __main__ import prime")
print(prime(1000))
print(f"Поиск тысячного простого числа: {test_2.timeit(number=500)}")

test_3 = Timer("prime_erato(100)", "from __main__ import prime_erato")
print(prime_erato(100))
print(f"Поиск сотого простого числа Эратосфен: {test_3.timeit(number=500)}")
test_4 = Timer("prime_erato(1000)", "from __main__ import prime_erato")
print(prime_erato(1000))
print(f"Поиск тысячного простого числа Эратосфен: {test_4.timeit(number=500)}")


"""
100 по счету простое число: 541
Поиск сотого простого числа: 0.24751422299959813
1000 по счету простое число: 7919
Поиск тысячного простого числа: 17.4055352510004
100 по счету простое число: 541
Поиск сотого простого числа Эратосфен: 13.904102360000252
1000 по счету простое число: 7919
Поиск тысячного простого числа Эратосфен: 13.899494413999491

Эратосфен гораздо медленнее на низких значениях i-того числа, и начинает 
выигрывать в скорости лишь при больших значениях.
Отчасти связано с тем, что для эратосфена я не придумал как не генерировать
предварительно весь чисельный ряд, и находить в его рамках абсолютно все простые числа,
а для не-эратосфена я формирую ряд только до нужного мне i-го по счёту простого числа.
"""