Section21.1First Steps

It might seem at first there is very little we can say about this function; after all, thus far we've seen no particular pattern in the primes themselves (other than that they are nearly all odd).

Remark21.1.1

Sage note:
The syntax for this function is prime_pi(n).

Strange as it may seem, and contrary to what I just implied, there are exact formulas for this function. The following formula is one of my favorites \[\pi(n)=-1+\sum_{j=3}^{n}\left((j-2)!-j\left\lfloor\frac{(j-2)!}{j}\right\rfloor\right)\, .\] Can you see why this is not useful in practice?

But it works!

Remark21.1.2

Sage note:
Don't forget that just because an algorithm works, doesn't guarantee it will be useful in practice! However, it's often useful to get something correct first, and only then try to optimize.

Remark21.1.3

Sage note:
It's possible to significantly speed up many such computations by converting to Cython, a way to take Python/Sage and turn it into the much-faster compiled language C. For a project, try to speed this function up using Cython!

More seriously, we can find a very rudimentary bound on this function.

As you can see below, this is not a very useful bound, considering there are actually 25 primes less than 100, not 3!

Although it may not seem evident, you should know that it is not necessary to actually find all the first \(n\) primes (even of a particular type) to compute how many there are, at least not always. If we define \(\phi(n,a)\) to be the number of positive integers less than \(n\) which are not divisible by any of the first \(a\) primes, then it is possible to develop the recursive formula \[\phi(n,a)=\phi(n,a-1)-\phi\left(\left\lfloor\frac{n}{p_a}\right\rfloor,a-1\right)\, ,\] which allows us to sort of use induction to compute \(\phi(n,a)\) without having to use much space.

Then it turns out that \[\pi(n)=\pi(\sqrt{n})+\phi(n,\pi(\sqrt{n}))-1\, ,\] which is also not hard to prove (by a counting argument). That is the typical way to count \(\pi\) without actually counting primes, and with some speedups is quite efficient.

This is also how one finds the \(n\)th prime. You use an approximation to the \(n\)th prime like \(n\ln(n)\) and then check \(\pi(n)\) near there to figure out exactly where it is.