Reducing the Space Used by the Sieve of Eratosthenes When Factoring
<|reference_start|>Reducing the Space Used by the Sieve of Eratosthenes When Factoring: We present a version of the sieve of Eratosthenes that can factor all integers $\le x$ in $O(x \log\log x)$ arithmetic operations using at most $O(\sqrt{x}/\log\log x)$ bits of space. This is an improved space bound under the condition that the algorithm takes at most $O(x\log\log x)$ time. We also show our algorithm performs well in practice.<|reference_end|>
@article{hartman2024reducing,
    title={Reducing the Space Used by the Sieve of Eratosthenes When Factoring},
    author={Samuel Hartman and Jonathan P. Sorenson},
    journal={arXiv preprint arXiv:2406.09150},
    year={2024},
    doi={10.1016/j.ipl.2024.106537},
    archivePrefix={arXiv},
    eprint={2406.09150},
    primaryClass={cs.DS math.NT}
}