This book provides a motivated introduction to sieve theory. Rather than focus on technical details which obscure the beauty of the theory, the authors focus on examples and applications, developing the theory in parallel. Suitable for a senior level undergraduate course or an introductory graduate course in analytic number theory. Preface xi Some basic notions 1(14) The big `O' and little `o' notation 1(1) The Mobius function 2(2) The technique of partial summation 4(1) Chebycheff's theorem 5(5) Exercises 10(5) Some elementary sieves 15(17) Generalities 15(2) The larger sieve 17(4) The square sieve 21(4) Sieving using Dirichlet series 25(2) Exercises 27(5) The normal order method 32(15) A theorem of Hardy and Ramanujan 32(3) The normal number of prime divisors of a polynomial 35(3) Prime estimates 38(2) Application of the method to other sequences 40(3) Exercises 43(4) The Turan sieve 47(16) The basic inequality 47(2) Counting irreducible polynomials in Fp [x] 49(2) Counting irreducible polynomials in Z[x] 51(2) Square values of polynomials 53(2) An application with Hilbert symbols 55(3) Exercises 58(5) The sieve of Eratosthenes 63(17) The sieve of Eratosthenes 63(2) Mertens' theorem 65(3) Rankin's trick and the function ?(x, z) 68(2) The general sieve of Eratosthenes and applications 70(4) Exercises 74(6) Brun's sieve 80(33) Brun's pure sieve 81(6) Brun's main theorem 87(13) Schnirelman's theorem 100(6) A theorem of Romanoff 106(2) Exercises 108(5) Selberg's sieve 113(22) Chebycheff's theorem revisited 113(5) Selberg's sieve 118(6) The Brun--Titchmarsh theorem and applications 124(6) Exercises 130(5) The large sieve 135(21) The large sieve inequality 136(3) The large sieve 139(3) Weighted sums of Dirichlet characters 142(5) An average result 147(4) Exercises 151(5) The Bombieri--Vinogradov theorem 156(21) A general theorem 157(10) The Bombieri--Vinogradov theorem 167(5) The Titchmarsh divisor problem 172(2) Exercises 174(3) The lower bound sieve 177(24) The lower bound sieve 177(8) Twin primes 185(8) Quantitative results and variations 193(2) Application to primitive roots 195(4) Exercises 199(2) New directions in sieve theory 201(17) A duality principle 201(4) A general formalism 205(2) Linnik's problem for elliptic curves 207(2) Linnik's problem for cusp forms 209(4) The large sieve inequality on GL(n) 213(3) Exercises 216(2) References 218(4) Index 222