Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2007/ii/paper-4/1f/solution

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 is
By 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 .
For , the sieving primes are . The surviving count is . Consequently

New to topics? Read the docs here!