解法と思考回路

まず、$p, q$の対称性を野放しにしておくと厄介なので、そこを固めておきます。

ある数が素数かどうかを判定するとき最初に見る事は、偶数であるかどうかです。素数であるかどうかを判定しようとする姿勢から$p, q$がどちらも偶数、奇数である場合も除く事を発見できます。

正直ここまで細かく書くと次の展開が見えますが、そうでない場合もあるので、一旦脳をリセットして考えます。
ここから$q$が何のときに $p^q + q^p$ が素数になるのか全然予想もつかないので、ここで「いろいろ試す」をします。
代入という作業をしてみましょう。$N=2^q + q^2$とします。 \begin{gather} q=3 の時 \\ N = 8 + 9 = 17 \\ q=5 の時\\ N = 32 + 25 = 57 = 3 \times 19 \\ q=7 の時\\ N = 128 + 49 = 177 = 3 \times 59 \\ q=11 の時 \\ N = 2048 + 121 = 2169 = 3 \times 723 \end{gather} これだけ結果が出れば、$q = 3$ 以外の時, $N$が3の倍数になることは予想できます。3の倍数の判定は、各桁の足し算をするだけですので、他より余計に気が付きやすいですね。
この予想が正しければ、解が導けます。実際正しいので、最後まで書きます。