Legendre's Formula for counting the number of primes less than \(n\) makes use of the inclusion-exclusion principle to avoid explicitly counting every prime up to \(n\). It is given by:
$$\pi(x) = \pi(\sqrt x) + \Phi(x, \sqrt x) - 1$$
Where \(\Phi(x, a)\) is the number of positive integers less than or equal to \(x\) that are relatively prime to the first \(a\) primes (i.e. not divisible by any of the first \(a\) primes). It is given by the recurrence relation (\(p_a\) is the \(ath\) prime (e.g. \(p_4 = 7\))):
$$\Phi(x, a) = \Phi(x, a - 1) + \Phi(x / p_a, a - 1)$$
This algorithm implements five modifications developed by Kim Walisch for calculating \(\Phi(x, a)\) efficiently.
Cache results of \(\Phi(x, a)\)
Calculate \(\Phi(x, a)\) using \(\Phi(x, a) = (x / pp) * \phi(pp) + \Phi(x mod pp, a)\) if \(a <= 6\)
Calculate \(\Phi(x, a)\) using \(\pi(x)\) lookup table
Calculate all \(\Phi(x, a) = 1\) upfront
Stop recursion at \(6\) if \(\sqrt x >= 13\) or \(\pi(\sqrt x)\) instead of \(1\)