Can't understand source of constant for prime counting function:

Question

Consider the prime counting function

$$ \pi(x) = \ the \ number \ of \ primes \ less \ than \ or \ equal \ to \ x$$

It is well known due to the sieve eratosthenes that given an integer $n$ and the set of primes less than or equal to $\sqrt{n} = p_1, ... p_k$ that the total number of additional primes generated is:

$$ A(n)= n - \sum_{i = 1}^{k}\left[ \frac{n}{p_i} \right] +\sum_{i = 1, j \ne i, j = 1}^{k,k}\left[ \frac{n}{p_i p_j} \right] ... $$

Based on simple inclusion and exclusion:

Therefore naturally I would assume that

$$\pi(\sqrt{n}) + A(n) = \pi(n)$$

That is primes less than the the root of n plus primes bigger than the root of n but less than n gives all the primes less than n.

But instead the formula in this wiki page: http://en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_.CF.80.28x.29 asserts what I have is:

$$\pi(n) + 1 = \pi(\sqrt{n}) + A(n)$$

Where is this '1' coming from?

Answer 1

You never sieved out $1$, and $1$ is not prime.

Answer 2

Let $p_1, \ldots, p_l$ denote the primes less than or equal to $n$. Then $\pi(\sqrt n) = k$, $\pi(n) = l$. $A(n)$ now counts the numbers less than $n$, which are not divisible by any of the primes $p_1, \ldots, p_k$. These are exactly the primes $p_{k+1}, \ldots, p_l$, and $1$. So $A(n) = l-k + 1$.