Definition: Sieve, Sieve Problem

A sieve is a tuple $(\mathcal A_N,\mathcal P_\rho,\mathcal R)$ consisting of * $\mathcal A_N:=\{a_1,\ldots,a_N\}\subset\mathbb N$, i.e. a subset of $N$ (not necessarily consecutive) natural numbers, * $\mathcal P_\rho:=\{p_1,\ldots,p_\rho\}\subset\mathbb P$, i.e. a subset of $\rho$ (not necessarily consecutive) prime numbers. * $\mathcal R$ is a union of congruence classes. $$\mathcal R:=\bigcup_{r=1}^\rho\bigcup_{j=1}^{k_r}R_{r}^{(j)},$$ where for $r=1,\ldots,\rho$, some $k_r$ congruence classes $R_r^{(1)},\ldots,R_r^{(k_r)}$ are given modulo each prime number $p_r$.

Given a sieve, a sieve problem is the problem of estimating the cardinality of all elements of $\mathcal A$ that are not congruent to any of the residue classes in $\mathcal R$, i.e. the number $$S(N):=|\{n\in\mathbb N\mid a_n\not\in R\}|.$$

Thank you to the contributors under CC BY-SA 4.0!




  1. Halberstam, H; Roth, K.F.: "Sequences", Oxford at the Claredon Press, 1966
  2. Schwarz, Wolfgang: "Einf├╝hrung in Siebmethoden der analytischen Zahlentheorie", B.I.-Wissenschaftsverlag, 1974