Let $a$ and $b$ be positive integers such that $a>b$ and the difference between $a^2+b$ and $a+b^2$ is prime. Compute all possible pairs $(a,b)$.

1. Let \( p \) be a prime number such that \( p = a^2 + b - (a + b^2) \). Simplifying this, we get:
   \[
   p = a^2 + b - a - b^2 = a^2 - a + b - b^2
   \]
2. We can factor the expression \( a^2 - a + b - b^2 \) as follows:
   \[
   p = (a - b)(a + b - 1)
   \]
3. Since \( p \) is a prime number, the product \((a - b)(a + b - 1)\) must equal \( p \). Given that \( a \) and \( b \) are positive integers and \( a > b \), we have \( a - b \geq 1 \). 

4. Since \( p \) is prime, one of the factors must be 1. Therefore, we consider the following cases:
   - Case 1: \( a - b = 1 \)
   - Case 2: \( a + b - 1 = 1 \)

5. For Case 1: \( a - b = 1 \)
   - Substituting \( a = b + 1 \) into the equation \( p = (a - b)(a + b - 1) \), we get:
     \[
     p = (b + 1 - b)((b + 1) + b - 1) = 1 \cdot (2b) = 2b
     \]
   - Since \( p \) is a prime number, \( 2b \) must be prime. The only even prime number is 2, so \( 2b = 2 \) which implies \( b = 1 \).
   - Substituting \( b = 1 \) back into \( a = b + 1 \), we get \( a = 2 \).
   - Therefore, one possible pair is \( (a, b) = (2, 1) \).

6. For Case 2: \( a + b - 1 = 1 \)
   - Simplifying, we get \( a + b = 2 \). Since \( a \) and \( b \) are positive integers and \( a > b \), the only possible values are \( a = 1 \) and \( b = 1 \), which contradicts \( a > b \). Therefore, this case does not provide any valid solutions.

7. Thus, the only possible pair \((a, b)\) that satisfies the given conditions is \((2, 1)\).

The final answer is \(\boxed{(2, 1)}\)