# Задание 2.

# Написать два алгоритма нахождения i-го по счёту простого числа. Функция нахождения простого числа должна принимать
# на вход натуральное и возвращать соответствующее простое число. Проанализировать скорость и сложность алгоритмов.
# Первый — с помощью алгоритма «Решето Эратосфена».
# Примечание. Алгоритм «Решето Эратосфена» разбирался на одном из прошлых уроков. Используйте этот код и попробуйте
# его улучшить/оптимизировать под задачу.
# Второй — без использования «Решета Эратосфена».
# Примечание. Вспомните классический способ проверки числа на простоту.
# Пример работы программ:
# >>> sieve(2)
# 3
# >>> prime(4)
# 7
# >>> sieve(5)
# 11
# >>> prime(1)
# 2
# Примечание по профилированию кода: для получения достоверных результатов при замере времени необходимо исключить/
# заменить функции print() и input() в анализируемом коде. С ними вы будете замерять время вывода данных в терминал
# и время, потраченное пользователем, на ввод данных, а не быстродействие самого алгоритма.


import cProfile
import timeit
import math

def sieve(n): # Решето Эратосфена переработанное для того чтобы получать N-ое простое число
    if n < 5:
        k = 12
    else:
        k = round(n * math.log2(n))  # эмпирически выведена формула для ограничения первичной последовательности
    siv = [i for i in range(k)]
    siv[1] = 0
    for i in range(2,k):
        if siv[i] != 0:
            j = i + i
            while j < k:
                siv[j] = 0
                j += i
    result = [i for i in siv if i != 0]
    return (result[n-1])

def sieve1(n):
    if n < 5:
        k = 12
    else:
        k = round(n*math.log2(n))
    a = list(range(k))
    a[1] = 0
    lst = []
    i = 2
    while len(lst) < n:
        if a[i] != 0:
            lst.append(a[i]) # улучшение за счет того что по последовательности пробегаем пока не получим N-ое простое число
            for j in range(i, k, i):
                a[j] = 0
        i += 1
    return(lst[-1])

def prime(n):
    l = [2]
    k = 1
    m = 1
    while len(l) < n:
        k += 1
        for i in l:
            if k % i == 0:
                m = 0
                break
        if m ==0:
            m =1
        else:
            l.append(k)
    return l[-1]

def prime1(n):
    l = [2]
    k = 1
    m = 1
    while len(l) < n:
        k += 2 # сокращаем перебор за счет того что берем только нечетные числа
        if (k > 10) and (k % 10==5): # здесь еще не учитываем числа что оканчиваются на 5
            continue
        for i in l:
            if (i*i-1 > k) or (k == 3): # учитываем что перебирать надо только числа, не превосходящие корня из искомого
                l.append(k)
                break
            if k % i == 0:
                break
    return l[-1]
# cProfile.run('sieve(100000)')

setup_code = '''
from __main__ import sieve,prime,sieve1,prime1
import math
from __main__ import np
'''
test_sieve = '''
sieve(np)
'''
test_sieve1 = '''
sieve1(np)
'''
test_prime = '''
prime(np)
'''
test_prime1 = '''
prime1(np)
'''
np = 50
qty = 1000
test1 = timeit.repeat(stmt=test_sieve, setup = setup_code, repeat = 5, number = qty )
print(f'Время: {round(min(test1),7)} поиска {np} простого числа для {qty} повторений (Решето Эратосфена)')
test2 = timeit.repeat(stmt=test_prime, setup = setup_code, repeat = 5, number = qty )
print(f'Время: {round(min(test2),7)} поиска {np} простого числа для {qty} повторений (классическая проверка)')
test3 = timeit.repeat(stmt=test_sieve1, setup = setup_code, repeat = 5, number = qty )
print(f'Время: {round(min(test3),7)} поиска {np} простого числа для {qty} повторений (Решето Эратосфена +)')
test4 = timeit.repeat(stmt=test_prime1, setup = setup_code, repeat = 5, number = qty )
print(f'Время: {round(min(test4),7)} поиска {np} простого числа для {qty} повторений (классическая проверка +)')

# Время: 0.00265 поиска 5 простого числа для 1000 повторений (Решето Эратосфена)
# Время: 0.00217 поиска 5 простого числа для 1000 повторений (классическая проверка)
# Время: 0.00364 поиска 5 простого числа для 1000 повторений (Решето Эратосфена +)
# Время: 0.00175 поиска 5 простого числа для 1000 повторений (классическая проверка +)

# Время: 0.05659 поиска 50 простого числа для 1000 повторений (Решето Эратосфена)
# Время: 0.08730 поиска 50 простого числа для 1000 повторений (классическая проверка)
# Время: 0.05584 поиска 50 простого числа для 1000 повторений (Решето Эратосфена +)
# Время: 0.05610 поиска 50 простого числа для 1000 повторений (классическая проверка +)

# Время: 1.09159 поиска 500 простого числа для 1000 повторений (Решето Эратосфена)
# Время: 5.95079 поиска 500 простого числа для 1000 повторений (классическая проверка)
# Время: 1.05755 поиска 500 простого числа для 1000 повторений (Решето Эратосфена +)
# Время: 1.46885 поиска 500 простого числа для 1000 повторений (классическая проверка +)

# Время: 0.1702877 поиска 5000 простого числа для 10 повторений (Решето Эратосфена)
# Время: 5.8521829 поиска 5000 простого числа для 10 повторений (классическая проверка)
# Время: 0.1513942 поиска 5000 простого числа для 10 повторений (Решето Эратосфена +)
# Время: 0.3586373 поиска 5000 простого числа для 10 повторений (классическая проверка +)



# n	        Решето Эратосфена	Решето Эратосфена+  классическая проверка   классическая проверка+
# ------------------------------------------------------------------------------------------------
# 5	        0.00265	            0.00364             0.00217                 0.00175
# 50	    0.05659	            0.05584             0.08730                 0.05610
# 500	    1.09159	            1.05755             5.95079                 1.46885
# 5000	    17.02877	        15.13942            585.21829               35.86373

# Вывод:
# Для вычисления N-го простого числа при небольших N оба алгоритмы (Решето Эратосфена и Классическая проверка) близки
# по быстродействию, но при увеличении N - Решето Эратосфена быстрее работает (даже не смотря что Решето расчитывается
# с запасом).
# У Решета похоже линейная зависимость от N, у алгоритма с классической проверкой похоже на квадратичную зависимость.

# Улучшенная версия Решета Эратосфена (sieve1) дает прирост скорости при увеличении большего N (порядка 13 % на N = 5000
# за счет того что не перебираем до конца все решето)
# Улучшенная модель классической проверки (prime1) дает гораздо лучше прирост по скорости по сравнению с обычной
# (за счет более быстрого перебора и учитывая что перебирать надо только числа, не превосходящие корня из искомого) -
# на N =5000 прирост в 35 раз, что практически выводит на один порядок рассчета с Решетом Эартосфена,
# хотя Решето Эратосфена все равно представляет самый быстрый алгоритм.


