Abstract
Ideally, a prime sieve should minimize memory footprint and computational overhead. Using a mod-6 wheel (numbers of the form 6n±1) reduces the search space (mod-6 eliminates multiples of 2 and 3).
This paper presents a bit-packed sieve algorithm that maps four mod-6 residual pairs into a single byte, effectively compressing 24 integers into 8 bits of storage. We examine the recurring bit patterns inherent in this mapping and provide algorithms for the sieve. Leveraging this byte alignment, we introduce a computational optimization for determining the sieve start index (p^2), utilizing the number-theoretic property that for any prime p > 3, p^2 = 24n+1.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Recommended Citation
Padmavilasom, Priyesh, "Bit-Packed Prime Sieve: Optimization via Mod-6 Wheel Factorization and Byte Alignment", Technical Disclosure Commons, (February 17, 2026)
https://www.tdcommons.org/dpubs_series/9333