Return to Answer

Show that the function $$f(x)=\begin{cases}1,&\text{if $x$ is prime;}\\\0,&\text{otherwise}\end{cases}$$ is primitive recursive.

Then show that given any primitive recursive function $f:\mathbb N\to\mathbb N$, the function $g:\mathbb N\to\mathbb N$ such that $g(x)=\sum_{y=1}^xf(x)$ is also primitive recursive. Then adapt this to prove what you want.

In general, what you do to prove that a specific function is primitive recursive depends on the function---unsurprisingly.

There are, on the other hand, various necessary conditions for a function to be primitive recursive, which can be used to show that specific functions are not primitive recursive. This is how one shows, for example, that the Ackermann function is not primitive recursive: one shows that it grows too fast.

Show that the function $$f(x)=\begin{cases}1,&\text{if $x$ is prime;}\\\0,&\text{otherwise}\end{cases}$$ is primitive recursive.

Then show that given any primitive recursive function $f:\mathbb N\to\mathbb N$, the function $g:\mathbb N\to\mathbb N$ such that $g(x)=\sum_{y=1}^xf(y)$ is also primitive recursive. Then adapt this to prove what you want.

In general, what you do to prove that a specific function is primitive recursive depends on the function---unsurprisingly. I'd love to hear about non-trivial sufficient conditions of a general nature, though...

There are, on the other hand, various necessary conditions for a function to be primitive recursive, which can be used to show that specific functions are not primitive recursive. This is how one shows, for example, that the Ackermann function is not primitive recursive: one shows that it grows too fast.

Show that the function $$f(x)=\begin{cases}1,&\text{if $x$ is prime;}\\\0,&\text{otherwise}\end{cases}$$ is primitive recursive. Then show that given any primitive recursive function $f:\mathbb N\to\mathbb N$, the function $g:\mathbb N\to\mathbb N$ such that $g(x)=\sum_{y=1}^xf(x)$ is also primitive recursive. Then adapt this to prove what you want.

In general, what you do to prove that a specific function is primitive recursive depends on the function---unsurprisingly.

There are, on the other hand, various necessary conditions for a function to be primitive recursive, which can be used to show that specific functions are not primitive recursive. This is how one shows, for example, that the Ackermann function is not primitive recursive: one shows that it grows too fast.

Show that the function $$f(x)=\begin{cases}1,&\text{if $x$ is prime;}\\\0,&\text{otherwise}\end{cases}$$ is primitive recursive. 

Then show that given any primitive recursive function $f:\mathbb N\to\mathbb N$, the function $g:\mathbb N\to\mathbb N$ such that $g(x)=\sum_{y=1}^xf(x)$ is also primitive recursive. Then adapt this to prove what you want.

In general, what you do to prove that a specific function is primitive recursive depends on the function---unsurprisingly.

There are, on the other hand, various necessary conditions for a function to be primitive recursive, which can be used to show that specific functions are not primitive recursive. This is how one shows, for example, that the Ackermann function is not primitive recursive: one shows that it grows too fast.

Show that the function $$f(x)=\begin{cases}1,&\text{if $x$ is prime;}\\\0,&\text{otherwise}\end{cases}$$ is primitive recursive. Then show that given any primitive recursive function $f:\mathbb N\to\mathbb N$, the function $g:\mathbb N\to\mathbb N$ such that $g(x)=\sum_{y=1}^xf(x)$ is also primitive recursive. Then adapt this to prove what you want.

Show that the function $$f(x)=\begin{cases}1,&\text{if $x$ is prime;}\\\0,&\text{otherwise}\end{cases}$$ is primitive recursive. Then show that given any primitive recursive function $f:\mathbb N\to\mathbb N$, the function $g:\mathbb N\to\mathbb N$ such that $g(x)=\sum_{y=1}^xf(x)$ is also primitive recursive. Then adapt this to prove what you want.

In general, what you do to prove that a specific function is primitive recursive depends on the function---unsurprisingly.

There are, on the other hand, various necessary conditions for a function to be primitive recursive, which can be used to show that specific functions are not primitive recursive. This is how one shows, for example, that the Ackermann function is not primitive recursive: one shows that it grows too fast.