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

Our algebra teacher usually gives us a paper of $20-30$ questions for our homework. But each week, he tells us to do all the questions which their number is on a specific form.

For example, last week it was all the questions on the form of $3k+2$ and the week before that it was $3k+1$. I asked my teacher why he always uses the linear form of numbers... Instead of answering, he told me to determine which form of numbers of the new paper should we solve this week.

I wanted to be a little creative, so I used the prime numbers and I told everyone to do numbers on the form of $\lfloor \sqrt{p} \rfloor$ where $p$ is a prime number. At that time, I couldn't understand the smile on our teacher's face.

Everything was O.K., until I decided to do the homework. Then I realized I had made a huge mistake.$\lfloor \sqrt{p} \rfloor$ generated all of the questions of our paper and my classmates wanted to kill me. I went to my teacher to ask him to change the form, but he said he will only do it if I could solve this:

Prove that $\lfloor \sqrt{p} \rfloor$ generates all natural numbers.

What I tried: Suppose there is a $k$ for which there is no prime number $p$ that $\lfloor \sqrt{p} \rfloor=k$. From this we can say there exists two consecutive perfect squares so that there is no prime number between them. So if we prove that for every $x$ there exists a prime number between $x^2$ and $x^2+2x+1$ we are done.

I tried using Bertrand's postulate but it didn't work.

I would appreciate any help from here :)

Solution 1:

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.

Solution 2:

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.