note
davido
<blockquote><em><p>(2) hash access slows disproportionately whereas this lookup could just be an array. That array could be packed down to one bit per element for the most efficient storage, given that it has only boolean values. Lookup (and registration) can be achieved without unpacking from that using bit operators such as '<<' and '&', thereby winning on processing as well as storage. </p></em></blockquote>
<p>What you describe is a [https://en.wikipedia.org/wiki/Generating_primes#Prime_sieves|primes sieve]. One common prime generation technique is the [https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes|Sieve of Eratosthenes]. Another (sometimes slightly faster, but always more complicated) is the [https://en.wikipedia.org/wiki/Sieve_of_Atkin|Sieve of Atkin].
</p>
<p>I believe [danaj] has a blazing fast segmented sieve in [mod://Math::Prime::Util], and I have a pretty basic non-segmented Sieve of Eratosthenes implementation in [mod://Math::Prime::FastSieve].</p>
<div class="pmsig"><div class="pmsig-281137">
<br /><p>Dave</p>
</div></div>
1137324
1137350