Let's think like a programmer implementing the sieve of Eratosthenes. You can think of the sieve of Eratosthenes as starting with an infinite string of 1 bits,

Let's think like a programmer implementing the sieve of Eratosthenes. You can think of the sieve of Eratosthenes as starting with an infinite string of 1 bits, then for each prime p, you AND it with a periodic infinite string that's all 1's except for 0's at multiples of p. Then repeat until you get to sqrt(sieve_size), with the next p being the next 1 bit in the string. AND is associative so you could alternatively AND together several of the periodic strings first, then you get a string whose period is the product of the periods. Could you use that to optimize? Yes. For example if your big sieve is 1GB, naively you'd need to do four 1GB passes to knock out four consecutive primes, say 11, 13, 17, 19. But you can instead calculate the combined action of those primes by doing four passes over a (much smaller!) bit vector of size 11x13x17x19, then apply that in one pass over the main 1GB sieve. (I guess you'd want to tune the max size of the small bit vector based on your cache size.) Further optimizations are possible, e.g. you could special-case the smallest primes. With a trivial indexing change, you can have your sieve bits represent odd numbers only, and halve the memory requirement (or double the largest prime you can find with a fixed amount of memory). Subsequent primes (e.g. knocking out multiples of 3 so your bit vector only contains bits representing numbers of the form 6k±1) involve less trivial changes to the indexing logic with diminishing returns.