Okay. Now that we've moved on to thinking about divisor counts, let's reintroduce our wheel factorization technique. Do you remember our wheel factorization function?
Sure. It was a simple helper function that looked like this: $$h(j)= \begin{cases} 0 & \text{if } 2 | j \textrm{ or } 3 | j \textrm{ or } 5 | j \textrm{ or } 7 | j \textrm{ or } 11 | j \textrm{ or } 13| j \textrm{ or } 17| j \textrm{ or } 19 | j \\ 1 & \text{otherwise} \end{cases} $$ So it's only non-zero when $j$ isn't divisible by the first 8 primes.
Great. Now, we can immediately use that function to define new, altered divisor counting functions. They'll look like this:
$$D'_{ 1}( n ) = \sum_{\substack{t=23 \\ h(t)=1}}^n 1$$ $$D'_{ 2 }( n ) = \sum_{\substack{t=23 \\ h(t)=1}}^n \sum_{\substack{u=23 \\ h(u)=1}}^{\lfloor \frac{n}{t} \rfloor} 1$$ $$D'_{ 3 }( n ) = \sum_{\substack{t=23 \\ h(t)=1}}^n \sum_{\substack{u=23 \\ h(u)=1}}^{\lfloor \frac{n}{t} \rfloor} \sum_{\substack{v=23 \\ h(v)=1}}^{\lfloor \frac{n}{t \cdot u} \rfloor} 1$$And so on for $D'_{ k }( n )$. Hopefully the pattern should be obvious for larger values of $k$.
Okay. So right, we count divisors, but we skip numbers divisible by the first 8 primes. Just like in the recursive case. And we can count primes with these?
Yes. Swap out our non-wheel factorized versions of $D_k'(n)'$ with these new functions. Keep everything else the same. If we do that, we'll find that
$$\sum_{j=1} \frac{\mu(j)}{j} (\sum_{k = 1}^{ \lfloor \frac{\log n}{\log 2} \rfloor } \frac{( -1 )^{ k+1 }}{k}\cdot D'_{ k }( n^{\frac{1}{j}} )) = \pi(n) - \pi(19)$$Huh. So this doesn't count the first few primes, and we have to account for them manually, then?
Right. But obviously that's no real trouble. And code to execute all of this correctly looks like the following.
If you run this version of the algorithm, what do you see?
Well, just as before, adding the wheel massively speeds computation up, or so it certainly appears. On my old but fine laptop, the non-wheel algorithm computed $\pi(10^5)$ in around 1.56 seconds. Here, the algorithm computes $\pi(10^5)$ in .7 milliseconds, and it computes $\pi(10^9)$ in about .86 seconds. So... again, that's much faster.
Exactly. This is just mostly confirming our previous results with a wheel, although here the implementation of the wheel is much faster.
It really is a huge speed up.
It sure is. So it might surprise you that we can actually speed this up by vastly more without too much increase in complexity. Let's set aside the wheel for a second and turn to that.