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\}|.$$

| | | | | created: 2020-05-17 11:58:07 | modified: 2020-05-17 12:18:33 | by: *bookofproofs* | references: [8526], [8527]

[8526] **Halberstam, H; Roth, K.F.**: “Sequences”, Oxford at the Claredon Press, 1966

[8527] **Schwarz, Wolfgang**: “Einführung in Siebmethoden der analytischen Zahlentheorie”, B.I.-Wissenschaftsverlag, 1974