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


# Код ##################################################################################################################
# Алгоритм полного перебора. Обладает квадратичной вычислительной сложностью O(N ** 2) за счет вложенного цикла.
def bust(n):
    primes = []
    i = 2
    while len(primes) < n:
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            primes.append(i)
        i += 1
    return primes[-1]


# Алгоритм "Решето Эратосфена". Более эффективен, так как мы делим не на все предыдущие числа, а только на найденные
# простые и только те, чей квадрат больше текущего числа.
def sieve(n):
    primes = [(2, 4)]
    i = 2
    while len(primes) <= n:
        for (prime, square) in primes:
            if i >= square and i % prime == 0:
                break
        else:
            primes.append((i, i * i))
        i += 1
    prime, square = primes[-1]
    return prime


# Анализ timeit ########################################################################################################
import timeit
print("Алгоритм перебора")
print("N\tt, sec")
for i in [1, 10, 100, 1000, 2000, 5000]:
    print(i, '\t', timeit.timeit(f'bust({i})', number=10, setup='from __main__ import bust') / 10)

print("Решето Эратосфена")
print("N\tt, sec")
for i in [1, 10, 100, 1000, 2000, 5000]:
    print(i, '\t', timeit.timeit(f'sieve({i})', number=10, setup='from __main__ import sieve') / 10)

# Алгоритм перебора
# N     t, sec
# 1     0.0000013767
# 10    0.0000244033
# 100   0.0021018547
# 1000  0.2634281022
# 2000  1.1824219891
# 5000  8.5609818641

# Решето Эратосфена
# N     t, sec
# 1     0.0000015575
# 10    0.0000173142
# 100   0.0004625012
# 1000  0.0226580249
# 2000  0.0844551729
# 5000  0.4823767132


# Анализ cPython #######################################################################################################
import cProfile
print("Алгоритм перебора")
for i in [1, 10, 100, 1000, 2000, 5000]:
    print(f'{i}:')
    cProfile.run(f'bust({i})')

print("Решето Эратосфена")
for i in [1, 10, 100, 1000, 2000, 5000]:
    print(f'{i}:')
    cProfile.run(f'sieve({i})')

# Алгоритм перебора
# N     t, sec
# 1     0.000
# 10    0.000
# 100   0.002
# 1000  0.269
# 2000  1.221
# 5000  8.614

# Решето Эратосфена
# N     t, sec
# 1     0.000
# 10    0.000
# 100   0.001
# 1000  0.024
# 2000  0.089
# 5000  0.503
