Expand description
§Time Efficiency
A sieving algorithm for this data structure will consider “crossing it off as nonprime” be flipping the 1 into a 0. That is, the starter data will contain all ones, and we’ll cross them off as nonprime by flipping them to zero.
With the Sieve of Eratosthenes, when we encountered a prime (2, for example), we then kept adding it by itself and crossing off those results as nonprime. (4, 6, 8, …).
However, this data that we’re defining does not store numbers divisible by 2, 3, or 5. That is, if we find some prime P, it makes no sense to “flip the 2P bit” because there is no bit in our data structure that represents 2P because 2P is divisible by 2. If we add P to that again, we get 3P, which also doesn’t have a bit to it because it’s divisible by 3.
The only numbers that have a bit matching their value is numbers of the form XP, where X is not divisible by 2, 3, or 5 (saying this over and over is getting repetitive. From now on, we’ll call those “coprime with 30”, or simply “30-coprime”).
If we only iterate over 30-coprime numbers, multiply them by P, and flipping the bit matching the result to 0, we’re making things 3.75x faster (30/8).