Algorithm for the Prime counting function

In Counting Primes - Prime Counting function - Part III, we saw the function used to calculate the sum of all primes less than a given value and it's Mathematica code. Well, the Mathematica code is good enough but we can do better with C. But if we try to convert the code given into C, we run into a problem. In the given code, we have relied heavily upon Mathematica's in-built functions. But we can sort the problem easily by using the some of the properties $\varphi_k(x,\pi(\sqrt{x}))$. First note that,

Result 1 : $\pi_k(x)=\varphi_k(x,\pi(\sqrt{x}))=\varphi_k(x,\sqrt{x})=\varphi_k(x,x-2)=\varphi_k(x,x-1)$, since $\pi(x) \leq x$.

Secondly, $\pi_k(x)$ increases only at prime values of $x$. This can be used to test the primality of $x$ in our C-code. Or casting it in different terms, we can say

Result 2 : $x$ is prime, if and only if $\pi_k(x) > \pi_k(x-1)$ (or) $\varphi_k(x,x-2) > \varphi_k(x-1,x-2)$.



The Algorithm to find $\pi_k(n)$ will now proceed as follows.

Input : Get the value of $n$.

Step 1: Create a table with 2 rows. Mark the first row as $m$ and fill it as $1,2,\cdots,\lfloor\sqrt{n}\rfloor, \lfloor n/\lfloor\sqrt{n}\rfloor\rfloor,\cdots,\lfloor n/2\rfloor,\lfloor n/1 \rfloor$. Mark the second row as $\varphi_k(m)$ and the fill the corresponding $\varphi_k(m,0)$ values.
Step 2 : Initiate $r=2$.
Step 3 : Check whether $r$ prime or not. To do this, compare the corresponding $\varphi$ entries of $r$ and $r-1$ (making use of Result 2).
Step 4 : If they are same, skip to Step 6. Else, conclude $r$ to be a prime.
Step 5 : For each $m\geq r^2$ , starting from the last entry and moving left, update the values of $\varphi_1$ using the recurrence, $\varphi_k(m)=\varphi_k(m)-r^k*(\varphi_k(\lfloor m/r \rfloor)-\varphi_k(r-1))$
Step 6 : Increment $r$.
Step 7: If $r$ equals $\lfloor\sqrt{n}\rfloor$, output the rightmost entry of the second row and Stop. Else, goto Step 3.



For example, the tables while computing $\pi_1(20)$ are given below.

TABLE 1 :: $\varphi_1(m,0)$
$
\begin{matrix}
m&1&2&3&4&5(=\lfloor20/4\rfloor)&6(=\lfloor20/3\rfloor)&10(=\lfloor20/2\rfloor)&20(=\lfloor20/1\rfloor)\\
\varphi_1(m)&0&2&5&9&14&20&54&209\\
\end{matrix}
$

TABLE 2 :: $\varphi_1(m,1)$
$
\begin{matrix}
m&1&2&3&4&5&6&10&20\\
\varphi_1(m)&0&2&5&5&10&10&26&101\\
\end{matrix}
$

TABLE 3 :: $\varphi_1(m,2)$
$
\begin{matrix}
m&1&2&3&4&5&6&10&20\\
\varphi_1(m)&0&2&5&5&10&10&17&77\\
\end{matrix}
$

Note a couple of things here. The table is modified $\pi(\lfloor\sqrt{n}\rfloor)$ times after the initialization. As a byproduct of the algorithm, we get the SumOfPrimes for all the entries in the first row. Also, we generate the list of primes $\leq \lfloor\sqrt{n}\rfloor$.

After I wrote this, I found that no text can really equal a cute demonstration in terms of clarity. So I found this, which will visualizes the algorithm's execution. Hope that clarifies things. I'll post the C-code for this algorithm in the next post.


Until then
Yours Aye
Me