Set of Prime Numbers is Primitive Recursive

Theorem

A prime number is defined as an element of $\N$ with exactly two positive divisors.

So, we have that $n > 0$ is prime if and only if $\map \tau n = 2$, where $\tau: \N \to \N$ is the divisor count function.

Thus we can define the characteristic function of the set of prime numbers $\Bbb P$ as:

$\forall n > 0: \map {\chi_\Bbb P} n := \map {\chi_{\operatorname {eq} } } {\map \tau n, 2}$

Now we let $g: \N^2 \to \N$ be the function given by:

$\map g {n, z} = \begin{cases}

0 & : z = 0 \\ \ds \sum_{y \mathop = 1}^z \map {\operatorname {div} } {n, y} & : z > 0 \end{cases}$

As:

it follows that $g$ is primitive recursive.

Then for $n > 0$:

$\ds \map g {n, n} = \sum_{y \mathop = 1}^n \map {\operatorname {div} } {n, y} = \map \tau n$

Then let $h: \N \to \N$ be the function defined as:

$\map h n = \map g {n, n}$

So we have, for all $n \in \N$:

$\map {\chi_\Bbb P} n = \map {\chi_{\operatorname {eq} } } {\map h n, 2}$

Hence the result.

$\blacksquare$