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 ответа
Формально алгоритм работает за константу, то есть за 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)
.
O(n*sqrt (n))
, поскольку время вызова is_prime(i)
осуществляется (b-a)
раз, где i
находится между [a, b]
и работает во время sqrt(i)
, если будем считать в общих случаях исключая все переменные, то это и будет худшим временем.
Реальное время намного ниже, поскольку оно пропускает много чисел за 1 или 2 операции, поэтому сложность в реальном времени составляет около O (n + (количество простых чисел) * sqrt (n))
, вы можете исследовать эту тему, чтобы достичь строгой формулы.