Prove a function is primitive recursive

This is not an exact answer, but it helps to quickly determine in many cases that a given function is primitive recursive. The idea is to use a reasonable programming language in which your function can be expressed more easily than with "raw" arithmetic and primitive recursion. Of course, the programming language must be limited enough to prevent unbounded searches and other constructs that lead to general recursion. I mention here just one easy possibility.

Suppose a function $f : \mathbb{N} \to \mathbb{N}$ is computed by a simple imperative program in polynomial running time (actually, as Grigory points out in his answer, any primitive recursive bound will do). More precisely, the program is allowed to use basic arithmetic operations, boolean values, variables, arrays, loops, and conditional statements. Then the function $f$ is primitive recursive.

The reason that such a program can only define a primitive recursive function is that the entire execution of the program may be encoded by a number $N$ whose bit size is bounded by a polynomial $p(n)$, where $n$ is the input. Because verifying that a number encodes the execution of a simple imperative program is primitive recursive, we can perform a bounded search up to $2^{p(n)}$ to find the number $N$ (such a bounded search is primitive recursive) and extract the answer from it.

Let us apply this to your question. The following Python program computes the function $\pi(n)$ and uses just a couple of loops and basic arithmetic (we could replace the remainder function % with another loop). Its running time is quadratic in $n$, assuming all basic operations are constant time:

def pi(n):
   '''Computes the number of primes which are less than or equal n.'''
   p = 0 # the number of primes found
   k = 2 # for each k we test whether it is prime
   while k <= n:
       j = 1 # possible divisors of k
       d = 0 # number of divisors of k found
       while j <= n:
           if k % j == 0: d = d + 1
           j = j + 1
       if d == 2: p = p + 1
       k = k + 1
   return p

Therefore your function is primitive recursive.

A conceptually simple test for whether a function is primitive recursive is whether or not you can write it in Bloop.

The crucial point is that the loop control flow structure forces you to say in advance how many times it will loop.

Here's some example code for working with primes written in Bloop.

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.