0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer and apologies for using the terms you disliked (I wasn't sure which terminology would've been better). I have some questions though: how would you get your values for M? Would you do it the same way I did to get prime_spoke_differences, or another way? And does your algorithm also work with numbers in the zeroeth turn? I.e., I understand it handles the seed primes as special cases, but how does it handle numbers up to the modulus P (i.e., with seeds 2, 3, 5, these would be the numbers 6 to 29)? Also, does it handle 0 and 1 as special cases too? $\endgroup$
    – nicoty
    Sep 9, 2021 at 9:40
  • $\begingroup$ Ah, I guess M is just the set of numbers containing 1 and prime numbers < P but excluding the numbers in the set S. And it seems like your algorithm does seem handle numbers less than P as well, so I guess there's no need to exclude those (except for the numbers 0, 1 and those in S). Anyways, thanks again! $\endgroup$
    – nicoty
    Sep 9, 2021 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.