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

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

Второй — без использования «Решета Эратосфена».
Примечание. Вспомните классический способ проверки числа на простоту.
Пример работы программ:
# >>> sieve(2)
# 3
# >>> prime(4)
# 7
# >>> sieve(5)
# 11
# >>> prime(1)
2

Примечание по профилированию кода: для получения достоверных результатов при замере времени необходимо
исключить/заменить функции print() и input() в анализируемом коде.
С ними вы будете замерять время вывода данных в терминал и время, потраченное пользователем, на ввод данных,
а не быстродействие самого алгоритма.
'''

import cProfile

# первый вариант
def sieve(n):
    number = 100
    sieve = [x for x in range(number)]
    sieve[1] = 0

    for x in range(2, number):
        if sieve[x] != 0:
            j = x * 2
            while j < number:
                sieve[j] = 0
                j += x

    results = [x for x in sieve if x != 0]
    return results[n-1]

# Провека рабочести кода
print(sieve(2))
print(sieve(5))

# второй вариант
def prime(n):
    number = 100
    results = [2]
    for x in range(3, number, 2):
        if x > 10 and x % 10 == 5:
            continue
        for j in results:
            if j*j-1 > x:
                results.append(x)
                break
            if x % j == 0:
                break
        else:
            results.append(x)
    return results[n-1]

# # Провека рабочести кода
# print(prime(4))
# print(prime(1))



# по сложности кода оба алгоритма практически идентичны

cProfile.run('sieve(10)')
cProfile.run('prime(10)')


# по скорости если решето Эратосфена проигрывает незначительно вначале, то при 10_000 диапазоне поиска простых чисел
# данный аглоритм выигрывает, связано это с тем, что во втором случае есть проверка на сравнение, что делается дольше

# 10 -> 1000 loops, best of 5: 1.87 usec per loop
# 100 -> 1000 loops, best of 5: 11.9 usec per loop
# 1000 -> 1000 loops, best of 5: 141 usec per loop
# 10000 -> 1000 loops, best of 5: 1.58 msec per loop

# prime
# 10 -> 1000 loops, best of 5: 1.13 usec per loop
# 100 -> 1000 loops, best of 5: 10.4 usec per loop
# 1000 -> 1000 loops, best of 5: 155 usec per loop
# 10000 -> 1000 loops, best of 5: 2.52 msec per loop


