An iterator for finding small (<= 1000000) primes.

for p in SmallSieve(1_000_000)
    println(p)
end

Uses n ÷ 30 bytes of memory. Skips 2, 3, and 5; starts at 7.

When applying the presieve buffer, we have to compute the offset in

For a prime number p and a multiple q, the wheel index encodes the prime number index of p and q modulo 30, which can be encoded to a single number from 1 ... 64. This allows us to jump immediately into the correct loop at the correct offset.

The {2, 3, 5}-wheel is efficient because it compresses memory perfectly (1 byte = 30 numbers) and removes 4/15th of all the multiples already. We don't get that memory efficiency when extending the wheel to {2, 3, 5, 7}, since we need to store 48 bits per 210 numbers, which is could be done with one 64-bit integer per 210 numbers, which in fact compresses worse (64 bits / 210 numbers) than the {2, 3, 5}-wheel (8 bits / 30 numbers).

What we can do however, is compute the repeating pattern that the first n primes create, and copy that pattern over. That is, we look at a the numbers modulo p₁ * p₂ * ⋯ * pₙ.

For instance, when presieving all multiples of {2, 3, ..., 19} we allocate a buffer for the range 1 : 2 * 3 * ... * 19 = 1:9699690. In a {2, 3, 5} wheel this means a buffer of 9699690 ÷ 30 = 323_323 bytes.

Full loop generates a potentially unrolled loop for a particular wheel that may or may not save the exit point.

Get segment i when dividing from:to into n pieces

The fan-in / fan-out phase that crosses off one multiple and then checks bounds; this is before and after the unrolled loop starts and finishes respectively.

For any prime number p we compute its prime number index modulo 30 (here wheel) and we generate the loop that crosses of the next 8 multiples that, modulo 30, are p * {1, 7, 11, 13, 17, 19, 23, 29}.

Population count of a vector of UInt8s for counting prime numbers. See https://github.com/JuliaLang/julia/issues/34059

Generates a sieving loop that crosses off multiples of a given prime number.

@sieve_loop :unroll :save_on_exit
@sieve_loop