Jak zmniejszyć złożoność przestrzeni w sicie Eratostenesa, aby wygenerować liczbę pierwszą między aib?
Po przejściu niektórych z nichPosty SO, znalazłemSito Eratostenesa jest najlepszym i najszybszym sposobem generowania liczb pierwszych.
Chcę wygenerować liczby pierwsze między dwiema liczbami, powiedzmya
ib
.
AFAIK, w metodzie Sieve, złożoność przestrzeni to O (b).
PS: Napisałem Big-O, a nie Theta, ponieważ nie wiem, czy wymagania dotyczące miejsca można zmniejszyć.
Czy możemy zmniejszyć złożoność przestrzeniSito Eratostenesa ?