Let $f(k)=k^{2}+k+n$. The problem is to prove its contrapositive: if there exists some $k(0 \leqslant k \leqslant n-2)$ such that $f(k)$ is not a prime, then there must be a $k_{0}\left(0 \leqslant k_{0} \leqslant\right.$ $\left.(n / 3)^{1 / 2}\right)$ such that $f\left(k_{0}\right)$ is not a prime. That is, if the set $S$ of all $k(0 \leqslant k \leqslant n-2)$ for which $f(k)$ is not a prime is not empty, then the smallest integer $k_{0}$ in $S$ must satisfy $0 \leqslant k_{0} \leqslant(n / 3)^{1 / 2}$.

(i) Thus, the problem is to estimate the size of the smallest $k_{0}$ from the fact that $f\left(k_{0}\right)$ is not a prime. This requires properties of the relationship between the divisors of $f(k)$ and the variable $k$. The most important and basic divisibility property of integer-coefficient polynomials is Example 4 in Chapter 1, Section 2. The key to solving this problem, besides cleverly using this property and the definition of primes, also involves utilizing special divisibility properties of specific polynomials. Below, we first discuss this.

Let $\boldsymbol{Z}[x]$ denote the set of all univariate integer-coefficient polynomials:
$$\begin{aligned} \boldsymbol{Z}[x]= & \left\{g(x)=a_{n} x^{n}+a_{n-1} x^{n-1}+\cdots+a_{j} x^{j}+\cdots\right. \\ & \left.+a_{1} x+a_{0}: a_{j} \in \boldsymbol{Z}, 0 \leqslant j \leqslant n, n \geqslant 0\right\} \end{aligned}$$

We have
$$\begin{aligned} g(y)-g(x)= & \left(a_{n} y^{n}+a_{n-1} y^{n-1}+\cdots+a_{j} y^{j}+\cdots+a_{1} y+a_{0}\right) \\ & -\left(a_{n} x^{n}+a_{n-1} x^{n-1}+\cdots+a_{j} x^{j}+\cdots+a_{1} x+a_{0}\right) \\ = & a_{n}\left(y^{n}-x^{n}\right)+a_{n-1}\left(y^{n-1}-x^{n-1}\right)+\cdots \\ & +a_{j}\left(y^{j}-x^{j}\right)+\cdots+a_{1}(y-x) \\ = & (y-x) h(x, y) \end{aligned}$$
where $h(x, y) \in \boldsymbol{Z}[x, y]$ (the set of bivariate integer-coefficient polynomials).
When $x, y$ are integer variables, we have
(a) $y-x \mid g(y)-g(x)$;
(b) $h(x, y) \mid g(y)-g(x)$.
(a) is the common divisibility property of polynomials (see Chapter 1, Section 2, Example 4), which can be easily generalized to multivariate integer-coefficient polynomials.

For special integer-coefficient polynomials, there are special relationships between them and their variables in terms of divisibility, which is characterized by (b). This is very important. For example, for $f(x)=x^{2}+x+n$, we have
$$f(x)-f(y)=(x-y)(x+y+1)$$

Thus,
$$x+y+1 \mid f(x)-f(y)$$

When $a \mid x+y+1$, then $a \mid f(x)-f(y)$. Furthermore, if $a \mid f(x)$, then $a \mid f(y)$.

Next, we specifically analyze the divisor properties of the polynomial $f(k)=k^{2}+k+n$.
(ii) From
$$n=f(0) \leqslant f(k)=k^{2}+k+ny$$. From
$$f(x)-f(y)=(x-y)(x+y+1)$$

we can see: (a) if $d \mid f(x), d \mid x-y$, then $d \mid f(y)$; (b) if $d \mid f(x), d \mid x+y+1$, then $d \mid f(y)$ (this is the special divisibility property of the polynomial $f(k)$). Whether (a) or (b), the choice of the size of $y$ can be appropriately controlled. In (a), we can take $y=x-sd$, and in (b), we can take $y=-(x+1)+td$.
(iv) If the set $S$ is not empty, let $k_{0}$ be the smallest $k$ in $S$ such that $f(k)$ is not a prime. Suppose
$$f\left(k_{0}\right)=p_{0} a, \quad p_{0} \text{ is the smallest prime factor of } f\left(k_{0}\right),$$

it is clear that
$$p_{0} \leqslant a, \quad p_{0}^{2} \leqslant f\left(k_{0}\right)<n^{2}$$

Using (iii), we can discuss the relationship between $k_{0}$ and $p_{0}$, i.e., control the size of $k_{0}$ by $p_{0}$, and estimate the upper bound of $p_{0}$ by $p_{0}^{2} \leqslant f\left(k_{0}\right)$. This is the approach to solving this problem.