Достаточно доказать, что если среди чисел от 0 до $q-2$ есть такое $k$, что $f(k)=k^2+k+q$ — составное, то такое число есть и в промежутке от 0 до $\sqrt{\dfrac q3}$.
Пусть $y$ — наименьшее целое неотрицательное число, такое что $f(y)$ — составное. Обозначим через $p$ наименьший простой делитель $f(y)$, тогда $f(y)\ge p^2$. Ниже мы докажем, что если $y\le q-2$, то $p\ge2y+1$, ввиду чего
$$
y^2+y+q\ge(2y+1)^2=4y^2+4y+1,
$$
и, следовательно, $y^2\lt\dfrac q3$, т. е. $y\lt\sqrt{\dfrac q3}$.
Итак, остаётся доказать, что $p\ge2y+1$ при $y\le q-2$.
Предположим противное: $p\le2y$ и рассмотрим разность
$$
f(y)-f(x)=(y-x)(y+x+1).
$$
Когда $x$ изменяется от 0 до $y-1$, выражение $y-x$ принимает значения $y$, $y-1$, $\ldots$, 1, а $y+x+1$ — значения $y+1$, $y+2$, $\ldots$, $2y$. Следовательно, при некотором $x$, $0\le x\le y-1$, число $f(y)-f(x)$ делится на $p$. Но в силу выбора $y$ и $p$ число $f(y)$ делится на $p$, а $f(x)$ — простое, поэтому $f(x)$ должно быть равно $p$. В то же время
$$
y-x\lt y+x+1\le q+x-1\lt q+x+x^2=f(x),
$$
поэтому $p=f(x)$ не может делить $(y-x)(y+x+1)$. Противоречие.
Заметим, что результат задачи применим к знаменитому трёхчлену Эйлера $f(x)=x^2+x+41$: легко проверить, что $f(x)$ простое для $x=0$, 1, 2, 3, а отсюда $\Big($поскольку $\sqrt{\dfrac{41}3}\lt4\Big)$ следует, что $f(x)$ — простое для всех 40 целых $x$ от 0 до 39.
