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?