А это даже я могу доказать, а не только Марина Юденич.

Единственный вопрос - считать ли нуль натуральным числом?

Если не считать, то:

- для 1: между 1^2 и (1+1)^2, т.е. 1 и 4, есть простое число 3.
- для 2: между 2^2 и (2+1)^2, т.е. 4 и 9, есть простое число 7.
- для 3: между 3^2 и (3+1)^2, т.е. 9 и 16, есть простое число 13.

А для остальных и подавно найдется.