Wheel factorization

Choose a modulus $W$ that is a product of small primes. Every prime not dividing $W$ must be coprime to $W$, so a search can restrict candidates to the corresponding residue classes modulo $W$. For several linear polynomials, discard each residue class in which any required value is divisible by a selected prime. The surviving residue classes can be combined using the Chinese remainder theorem.

The wheel modulus is the product $W$ of a chosen finite set of small distinct prime numbers in wheel factorization. Except for those primes themselves, every prime candidate must lie in a residue class coprime to $W$. For $W=2\cdot 3\cdot 5=30$, the allowed residues are $1,7,11,13,17,19,23,29$, repeating every thirty integers. The proportion retained is $\phi (W)/W$. Passing the wheel only avoids these small divisors; it does not certify primality, since composite values such as $49$ still pass.