Is the Legendre sieve explicit?

Question

The Wikipedia page for the Legendre sieve...

http://en.wikipedia.org/wiki/Legendre_sieve

...says that the Legendre sieve gives upper and lower bounds on the number of primes in a given range. In particular, there is an inequality towards the bottom of the page that says that the Legendre sieve can be used to give an upper bound on the prime counting function.

However, I've tested the Legendre sieve for some arbitrary values (namely 10, 28, and 100) and have gotten explicit values for $\pi(x)$. This makes sense, too, since the sieve is just based on elementary counting principles and inclusion/exclusion. Where, then, does the estimation error come from, or what is Wikipedia referring to?

Many thanks!

Answer 1

If $z$ is too small, you may "forget" to strike out some composites (having only prime factors larger than $z$). Therefore if $z$ is too small you only get $S(\{1,\ldots,x\},z\#) \ge \pi(x)-\pi(z)+1$. For example, with $z=3$, we find that $S(A,P)=\lfloor x\rfloor -\lfloor \frac x2\rfloor -\lfloor \frac x3\rfloor + \lfloor \frac x6\rfloor$, hence $$\pi(x)\le \lfloor x\rfloor -\lfloor \frac x2\rfloor -\lfloor \frac x3\rfloor + \lfloor \frac x6\rfloor+1$$ as a very simple and very rough estimate. For example, this says $\pi(100)\le 100-50-33+16+1=34$, whereas $\pi(100)=25$. Clearly, the error starts growing from $x=25$ onward.

Answer 2

Yes the Legendre sieve is explicit and will give the exact count of prime numbers in the interval $[\sqrt x, x]$. However, to derive analytic expressions and bounds from the sieve we have to remove the difficult-to-work-with floor function for each term so that a term such as $\lfloor \frac{x}{p_1} \rfloor$ now becomes $\frac{x}{p_1}$. By doing so though we have introduced an error $\epsilon$ such that $0 \geq \epsilon > 1$. If we are sieving with $n$ primes there are $2^n$ terms leading to an error which is at most $\pm 2^{n-1}$; a very large error!

So yes, when using the explicit form of the sieve we can calculate $\pi(x) - \pi(\sqrt x) + 1$ exactly. It's just when we want to derive an analytic expression or bound for the prime counting function that things become less explicit.