0
from math import log2, gcd

a = 2**30
b = 2**31
all_simple = []
all_log2 = []
all_paras = []
all_paras2 = []
final_paras = []
paras_counter = 0


def is_prime(num):
    if num == 1:
        return False
    for p in range(2, int(num**0.5)+1):
        if num % p == 0:
            return False
    return True


for i in range(a, b+1):
    if is_prime(i):
        all_simple.append(i)

2 ответа 2

2

Формально алгоритм работает за константу, то есть за O(1), ибо в нём зафиксированы параметры a и b, но будем считать их переменными.

Функция is_prime() являет собой простую проверку числа на простоту путём перебора делителей до sqrt(num). Сложность O(sqrt(num)) в худшем случае, то есть когда функции подаётся простое число.

Дальше идёт цикл, в котором перебираются числа от a до b включительно, простые из них закидываются в массив; append(), если не ошибаюсь, работает в среднем за O(1). Сразу сделаем верхнюю оценку в виде O((b - a) * sqrt(b)). Но по факту алгоритм работает гораздо быстрее, так как полный перебор делителей до sqrt(N) будет осуществляться лишь для простых чисел, которых всё меньше и меньше при стремлении к бесконечности.

Обратимся к статье о распределении простых. Там говорится, что количество простых на отрезке [1; n] растёт примерно как n / ln(n). Адаптировав для нашего случая, получим, что на отрезке от a до b будет примерно b / ln(b) - a / ln(a) простых, на которых будут перебираться все делители до корня. Получим примерную нижнюю оценку вида O((b - a) + (b / ln(b) - a / ln(a)) * sqrt(a)). Здесь мы не учли случаи, когда на простоту проверяется квадрат простого — на них is_prime() будет работать тоже достаточно долго.

Простите, я, наверное, довольно сумбурно написал. Дать точную оценку здесь весьма сложно из-за природы простых чисел.

Вообще получить список простых можно быстрее, применив решето Эратосфена (если достаточно маленькие числа и хватает памяти, но это не случай автора вопроса) или алгоритмы проверки на простоту (приведенный в коде is_prime() проверяет через факторизацию) — Ферма, BPSW и множество других, но среди них много вероятностных и есть ломающиеся на особых числах — к примеру, тест Ферма не работает на числах Кармайкла. На худой конец, есть алгоритм Полларда, факторизующий за O(N^1/4).

1

O(n*sqrt (n)), поскольку время вызова is_prime(i) осуществляется (b-a) раз, где i находится между [a, b] и работает во время sqrt(i), если будем считать в общих случаях исключая все переменные, то это и будет худшим временем.

Реальное время намного ниже, поскольку оно пропускает много чисел за 1 или 2 операции, поэтому сложность в реальном времени составляет около O (n + (количество простых чисел) * sqrt (n)), вы можете исследовать эту тему, чтобы достичь строгой формулы.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.