Large sieve

Summary

The large sieve is a method of analytic number theory. It applies when a set of integers is sifted by many residue classes modulo each prime. Its core is an inequality for exponential sums: a trigonometric polynomial cannot be large at many well-spaced points at once. In arithmetic form it bounds the size of a set of integers that misses many residue classes modulo many primes. It is a key tool in the proof of the Bombieri–Vinogradov theorem.