3.9 Try to find all numbers of the form $p^{p}+1$ that are prime and have no more than 19 digits ($p$ is a natural number).
(28th Moscow Mathematical Olympiad, 1965)
［Solution］Obviously, $p1000^{6} \cdot 16=16 \cdot 10^{18},
$

Therefore, $16^{16}+1$ has more than 19 digits.
If $p=8$, then
$
\begin{aligned}
8^{8}+1 & =2^{24}+1 \\
& =\left(2^{8}\right)^{3}+1 \\
& =\left(2^{8}+1\right)\left(2^{16}-2^{8}+1\right)
\end{aligned}
$

is a composite number.
If $p=4$, then
$4^{4}+1=257$ is a prime number.
If $p=2$, then
$2^{2}+1=5$ is a prime number.
Thus, the prime numbers sought are $2,5,257$.