Sage note21.1.1Syntax for counting primes
The syntax for this function is prime_pi(n).
Section21.1First Steps¶ permalink
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). You may wish to see what the function looks like to confirm this sense. It is a not particularly smoothly increasing function with no upper bound (recall Theorem 6.2.1).
Subsection21.1.1A funky formula
Given the skepticism of the paragraphs so far this chapter, you may be surprised to learn there are exact formulas for this function, as well as for the \(n\)th prime. The following formula (for \(n > 3\)) is one of my favorites (see the Appendix of the exhaustive Hardy and Wright, [C.1.2], and also Exercise 21.5.1): \begin{equation*}\pi(n)=-1+\sum_{j=3}^{n}\left((j-2)!-j\left\lfloor\frac{(j-2)!}{j}\right\rfloor\right)\, .\end{equation*} Can you see why this is not useful in practice? So there is plenty left for us to discuss.
On the other hand, it works! We can confirm this by using the following code.
Sage note21.1.2Cython
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!
Sage note21.1.3Not all algorithms are equal
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.
Subsection21.1.2A very low bound
On a more computationally feasible note, one can find a very rudimentary (lower) bound on this function. Recall that unadorned logarithms are the natural log.
Fact21.1.4
There are at least \begin{equation*}\frac{\log(\log(x)/\log(2))}{\log(2)}+1=\log_2(\log_2(x))+1\end{equation*} primes less than or equal to \(x\).
As you can see below, this is not a very useful bound, considering there are actually 25 primes less than 100, not 3!
Subsection21.1.3Knowledge from nowhere
Finally, 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.
Definition21.1.5
Let \(\phi(n,a)\) to be the number of positive integers less than \(n\) which are not divisible by any of the first \(a\) primes
Now it is possible to develop the recursive formula \begin{equation*}\phi(n,a)=\phi(n,a-1)-\phi\left(\left\lfloor\frac{n}{p_a}\right\rfloor,a-1\right)\, ,\end{equation*} which allows use a type of inductive argument to compute \(\phi(n,a)\) without having to use many computational resources.
It is then not too hard to use a counting argument to prove that \begin{equation*}\pi(n)=\pi(\sqrt{n})+\phi(n,\pi(\sqrt{n}))-1\end{equation*} This is the typical way to count \(\pi\) without actually counting primes, and with some speedups it can be quite efficient.
Interestingly, this is also how one finds the \(n\)th prime. You use an approximation to the \(n\)th prime like \(n\log(n)\) and then check values of \(\pi(n)\) near that point to see where the value changes, which should lead you exactly to the prime you seek. (Recall Sage note 4.2.1 about %time when using the following cell.)