📈 FROM O(...) TO O(...) Поиск всех простых до N: от O(n√n) до O(n log log n) Очевидное решение — проверять каждое число отдельно: def primes_up_to(n): return [i for i in range(2, n + 1) if is_prime(i)] O(√n) на каждое число. Суммарно — O(n√n). На миллионе чисел медленно. Решето Эратосфена: def sieve(n): is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(n**0.5) + 1): if is_prime[i]: for j in range(ii, n + 1, i): is_prime[j] = False return [i for i, v in enumerate(is_prime) if v] O(n log log n) — практически линейная. Идея: не проверяем делители, а вычёркиваем кратные. Каждое составное число вычёркивается ровно один раз. Начинаем с ii — всё меньшее уже вычеркнуто раньше. 🐍Вопросы с собесов -> ProstoPython