How to get the numbers in the Sieve of Eratosthenes with wheel factorisation?

Question

I'd like some help with figuring out the algorithm for the Sieve of Eratosthenes with wheel factorisation. Specifically, I need help figuring out if it's possible to convert between an index and the number its supposed to represent (or between an index and a spoke and turn pair), and if it is, how it'd be done. For more context, the way I'm thinking of implementing the algorithm would involve:

• Obtaining some seed primes from an implementation of the sieve without wheel factorisation (aka, the simple sieve) and calculating their product to obtain the modulus.
• Using a list of booleans (assume all indexing/numbering terminology I use are 0 based) to somehow represent numbers and their primality. The list's elements' values will be their primality and their indices will somehow be converted to and from the numbers.

The numbers the list will represent will only be the numbers >= the modulus (the primes < modulus will just be computed using the simple sieve) and are in the spokes of the wheel (aka columns of the table) that contain the numbers which are potentially prime, which would be determined by determining the prime numbers (using the simple sieve) in the first turn of the wheel (aka, the first row, or the one after the initial row). E.g., with seed primes 2 and 3, the spokes with potential primes would be the ones containing 7 and 11 in their first turn.

The current spoke, turn and index values will be tracked.

Currently, I can convert between the actual number and a pair of spoke and turn values, but my problem is that I'm not sure how I'd convert to and from an index in the list to the number that it's supposed to represent (or otherwise between an index and a spoke-turn pair). The reason why I want to convert between the number and index (or spoke-turn pair and index) is that there is a part of the simple sieve algorithm which involves iterating through the list starting from the index representing the square of the current prime by the current prime's multiples, which I'd also like to do in the version with wheel factorisation.

Is it even possible to do it this way, or would the list have to represent all the numbers instead of excluding the numbers that are obviously not prime (i.e., with seeds 2 and 3, these would be in spokes containing 6, 8, 9 and 10 in the first turn)? If not, how should I try to implement the sieve with wheel factorisation instead?

Answer 1

I really dislike the “spokes” and “wheels”, they just make things confusing.

I assume the Sieve of Eratosthenes is understood.

Let S be a set of primes, usually a small set of small primes. No prime is divisible by an element of S, except the members of S itself. We can therefore try to create a sieve that excludes all multiples of elements of S

Let P be the product of the elements of S. If we test whether kP + j is divisible by an element of S is independent on k and only depends on j, 0 <= j < P.

Let Q be the product of the elements of S minus 1. For example if S = { 2, 3, 5, 7 } then P = 2 * 3 * 5 * 7 = 210, and S = 1 * 2 * 4 * 6 = 48. It is reasonably obvious that k*P + j is not divisible by an element of S for exactly Q out of the P possible values for j. Let M be the set of values j, 0 <= j < P, which are not divisible by elements of S.

We now create a sieve, but not using 1 bit per integer, but Q bits for every group of P integers. Only Q bits corresponding to the numbers in M need to be stored, because if j is not in M then kP + j is composite (with the exception of the elements of S).

Given an integer p, we write p = kP + j, 0 <= j < P. To check if p is a prime, we use a table of length P which maps j to an index I if j is the I-th element of M, starting with 0, and to -1 if j is not in M. If I < 0 then p is not a prime, unless P is in S. otherwise, but #i in the k-th group of P bits is set if and only if p is a prime.

A bit position 0 <= I < Q is translated to I using another table of length Q. The I-th bit in the k-the group of bits corresponds to the integer k*P + j, where j is found by taking the I-th entry in the second table.

As an example. with S = { 2, 3, 5 }, P = 30, Q = 8, M = { 1, 7, 11, 13, 17, 29, 23, 29 }, the second lookup table is [ 1, 7, 11, 13, 17, 19, 23 29 ] and the first table is [-1. 0, -1, -1, -1, -1, -1, 1, -1, -1, -1, 2, -1, 3, -1, -1, -1, 4, -1, 5, -1, 1, -1, 6, -1, -1, -1, -1, -, 7].

To build the sieve, for numbers from 0 to nP - 1, we create a table with n groups of Q bits. The bit corresponding to 1 is cleared, all other bits are set. Multiples of elements if S need not be removed.