computer science - 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.