Reducing the Space Used by the Sieve of Eratosthenes When Factoring

TY - UNPB

T1 - Reducing the Space Used by the Sieve of Eratosthenes When Factoring

AU - Hartman, Samuel

AU - Sorenson, Jonathan P

N1 - 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.

PY - 2024/6

Y1 - 2024/6

UR - https://arxiv.org/abs/2406.09150

U2 - 10.48550/arXiv.2406.09150

DO - 10.48550/arXiv.2406.09150

M3 - Preprint

BT - Reducing the Space Used by the Sieve of Eratosthenes When Factoring

ER -