Como faço para reduzir a complexidade do espaço em Sieve of Eratosthenes para gerar primos entre a e b?
Depois de passar por alguns dosSO postagens, eu encontreiPeneira de Eratóstenes é a melhor e mais rápida maneira de gerar números primos.
Eu quero gerar os números primos entre dois números, digamosa
eb
.
AFAIK, no método de Sieve, a complexidade espacial é O (b).
PS: Eu escrevi Big-O e não Theta, porque não sei se o requisito de espaço pode ser reduzido.
Podemos reduzir a complexidade espacial emPeneira de Eratóstenes ?