Does $\lfloor \sqrt{p} \rfloor$ generate all natural numbers?

If we prove that for every x there exists a prime number between $x^2$ and $x^2+2x+1$, we are done.

This is Legendre's conjecture, which remains unsolved. Hence the big smile on your teacher's face.

Any of the accepted conjectures on sieves and random-like behavior of primes would predict that the chance of finding counterexamples to the conjecture in $(x^2, (x+1)^2)$ decrease rapidly with $x$, since they correspond to random events that are (up to logarithmic factors) $x$ standard deviations from the mean, and probabilities of those are suppressed very rapidly. This makes the computational evidence for the conjecture more reliable than just the fact of checking up to the millions and billions.