Is there a way to quickly iterate multiples of some prime $N$ while avoiding multiples of blacklisted primes $X$, $Y$, $Z$, ...? By quickly I mean is there a faster way than:
- Increment current number by N.
- Check if current number is divisible any each number in blacklist (M checks if there are M primes in the blacklist).
- If so, jump to 1, else return the current number as the next number in the iteration.
My end goal would be an O(1) algorithm that lets me answer queries like, "Give me the 5th number that is a multiple of N but not a multiple of X, Y, or Z." But the above algorithm requires computing the 1-4th numbers first, so it's linear time.
I suspect the answer is no because it seems that if there is a way it would allow speeding up the Sieve of Eratosthenes. Although in some cases the sieve avoids redundant marking by starting at a prime square, it still redundantly marks numbers sometimes. For example the sieve will wastefully mark 60 three times, once for 2, once for 3, and once for 5. You can see this by watching 60 light up three different colors in the linked Wikipedia article's first graphic: