Past exam of the mathematics course of the University of Cambridge 2005 ii Paper 3 1H Solution Created 2026-09-24 Updated 2026-10-14
Let be the first primes, and let count positive integers at most not divisible by any of them. The inclusion-exclusion principle givesFor , every composite at most is removed, so the survivors are one and the primes larger than . Thus the Legendre prime-counting formula is . This is the prime-counting formula, distinct from the factorial-valuation formula of the same name.
Fix and put . Every prime exceeding is among the unsieved integers. Replacing each floor in the finite sum by its argument makes an error bounded by , givingTake with fixed. The supplied product estimate gives . Since can be arbitrarily large, . The order of these limits avoids treating the growing inclusion-exclusion error as negligible.
Past exam of the mathematics course of the University of Cambridge 2007 ii Paper 4 1F Solution Created 2026-09-24 Updated 2026-10-14
Let be the primes not exceeding , where , and let count integers divisible by none of these primes. Every surviving integer other than is prime: a composite integer at most has a prime factor at most its square root. Conversely, the surviving primes are exactly those between and . Thus the Legendre prime-counting formula isBy inclusion-exclusion,where the empty product is one. To cover literally every positive real , replace the subtraction of by : for , both counts are zero and there is no surviving integer .
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 2 1G Solution Created 2026-09-24 Updated 2026-10-05
The Legendre prime-counting formula counts positive integers surviving a finite prime sieve. For , put and let be the primes at most . By inclusion-exclusion principle, the number of positive integers at most divisible by none of these primes isThe empty product is . Every composite number at most has a prime factor at most , so the survivors are precisely and the primes between and . ConsequentlyFor , the sieving primes are , andAs a direct check, the primes are .
Prime-counting function Created 2026-09-24 Updated 2026-11-05
The prime-counting function counts the prime numbers not exceeding a real bound :Thus , and . It is a nondecreasing step function with a jump of one at each prime number, and for .
Computing one large value is different from listing every prime number below it. A number-theoretic sieve can do both up to a moderate bound; Legendre prime-counting formula and the Lehmer prime-counting algorithm instead organize counts of allowable factors. The Prime number theorem describes the long-term scale , rather than exact individual jump locations.