Ниже — кратко про улучшения, их сложность и код.
1) Простой оптимизированный вариант: проверять делители только до $\sqrt{i}$ и пропускать чётные числа.
- Сложность: суммарно $O\left(n\sqrt{n}\right)$ (то же, что $O(n^{3/2})$), по сравнению с исходным $O(n^2)$.
- Почему быстрее: меньше проверок на делимость (до $\sqrt{i}$ вместо до $i-1$), и проверяем примерно вдвое меньше кандидатов, пропуская чётные.
Код:
def primes_trial(n):
if n < 2:
return []
res = [2]
for i in range(3, n+1, 2):
isprime = True
r = int(i**0.5)
for j in range(3, r+1, 2):
if i % j == 0:
isprime = False
break
if isprime:
res.append(i)
return res
2) Сито Эратосфена (рекомендую для большинства задач до больших n).
- Сложность по времени: $O\left(n\log \log n\right)$.
- Память: $O(n)$.
- Почему быстрее на практике: алгоритм помечает кратные простых массовыми операциями (меньше операций деления), хорошая локальность данных и возможность оптимизаций (байтовый массив, срезы), что в Python дает большой выигрыш.
Код (байтовое сито, эффективнее чем списковые проверки):
def primes_sieve(n):
if n < 2:
return []
sieve = bytearray(b'\x01') * (n + 1)
sieve[0:2] = b'\x00\x00'
r = int(n**0.5)
for p in range(2, r+1):
if sieve[p]:
start = p*p
sieve[start:n+1:p] = b'\x00' * ((n - start)//p + 1)
return [i for i, isprime in enumerate(sieve) if isprime]
3) Для очень больших $n$: сегментированное сито — делает те же пометки по блокам, использует память $O(\sqrt{n})$ и сохраняет время примерно $O(n\log \log n)$.
Краткое резюме:
- Если $n$ невелико (например, до нескольких сотен тысяч), trial-division с проверкой до $\sqrt{i}$ + пропуск чётных простых может быть простым и достаточным.
- Для больших $n$ лучше использовать сито Эратосфена (или сегментированное сито) — асимптотически и практически быстрее.