# Quick way to iterate multiples of a prime N that are not multiples of primes X, Y, Z, …?

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:

1. Increment current number by N.
2. Check if current number is divisible any each number in blacklist (M checks if there are M primes in the blacklist).
3. 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:

-

Up to $kN$ (inclusive) there are $k$ positive integer multiples of $N$, of which $\lfloor k/X \rfloor$ are multiples of $X$, etc. By inclusion-exclusion, the number that escape a "blacklist" of $3$ primes is $$k - \left\lfloor \frac{k}{X} \right\rfloor - \left\lfloor \frac{k}{Y} \right\rfloor - \left\lfloor \frac{k}{Z} \right\rfloor + \left\lfloor \frac{k}{XY} \right\rfloor + \left\lfloor \frac{k}{XZ} \right\rfloor + \left\lfloor \frac{k}{YZ}\right\rfloor - \left\lfloor \frac{k}{XYZ}\right\rfloor$$ Approximate it without the $\lfloor \cdot \rfloor$'s, and you're off by at most $4$, so then adjust...
EDIT: For example, suppose you want the $35$'th positive integer multiple of $N$ (any prime other than $5$, $7$ or $11$) that is not a multiple of $X=5$, $Y=7$ or $Z=11$. Thus you want $k$ so that $$f(k) = k - \left\lfloor \frac{k}{X} \right\rfloor - \left\lfloor \frac{k}{Y} \right\rfloor - \left\lfloor \frac{k}{Z} \right\rfloor + \left\lfloor \frac{k}{XY} \right\rfloor + \left\lfloor \frac{k}{XZ} \right\rfloor + \left\lfloor \frac{k}{YZ}\right\rfloor - \left\lfloor \frac{k}{XYZ}\right\rfloor = 35$$ Now \eqalign{k &- \frac{k}{X} - \frac{k}{Y} - \frac{k}{Z} + \frac{k}{XY} + \frac{k}{XZ} + \frac{k}{YZ} - \frac{k}{XYZ} \cr &= k \left(1-\frac{1}{X}\right)\left(1 -\frac{1}{Y}\right) \left( 1 - \frac{1}{Z}\right) = \frac{48 k}{77}} which would be $35$ for $k = 56.14\ldots$. Now $f(56) = 34$ so we try $f(57)$ and find that this is $35$. Thus $57N$ is the multiple of $N$ we are looking for.