A general [no-computers] solution:
First of all:
We are starting with 4000 and repeatedly replacing $n$ with $n-\lfloor\sqrt n\rfloor$. That is, if $n=m^2+k$ where $0\leq k\leq2m$ then we are subtracting $m$. Two cases: if $k<m$ then write our new number as $m^2-m+k=(m-1)^2+m-1+k$; if we repeat the procedure then we will have $(m-1)^2+k$ -- that is, doing our operation twice reduces $m$ by 1 and leaves $k$ unaltered. Alternatively, if $k\geq m$ then our new number is $m^2+k-m$ and repeating the procedure gives us $m^2-2m+k=(m-1)^2+k-1$ -- that is, doing our operation twice reduces $m$ by 1 and also reduces $k$ by 1. Note that in both cases we still have $k\leq2m$ after our two reduction steps except maybe in the latter case if $k=2m$ exactly. In that case, what happens is that we go $m^2+2m\rightarrow m^2+m\rightarrow m$ and instead of $(m-1,k-1)$ we have $(m,0)$.
If $0\leq k<m$ ("small $k$") then two iterations replace $(m,k)$ with $(m-1,k)$.
If $m\leq k<2m$ ("large $k$") then two iterations replace $(m,k)$ with $(m-1,k-1)$.
And if $k=2m$ ("maximal $k$") then two iterations replace $(m,k)$ with $(m,0)$.
Let's now consider iterating this.
If we start with "small $k$" then we can do $m-k$ small-$k$ steps, after which we have $(k,k)$ and we move to "large $k$" (or "maximal $k$" if $k=0$ but then we also have $n=0$ and are finished). The remaining large-$k$ iterations will take us cleanly down to $(0,0)$.
If we start with "large $k$" then we can do $2m-k$ large-$k$ steps, after which we have $(k-m,2(k-m))$, do one "maximal $k$ step, and are at $(k-m,0)$ and move to "small $k$". The remaining small-$k$ iterations will take us cleanly down to $(0,0)$.
The following diagram may help to illustrate what happens:
Here, two of the original iterations take one step along a red or green arrow, or jump all the way from tail to head of a blue one. So, if we start in red territory then we walk north until we cross the region boundary, then we walk northwest until we reach (0,0); if we start in green territory then we walk northwest until we reach the diagonal, then hop to the left edge and walk north to (0,0).
Let's now apply this to the present case.
We start at $4000=63^2+31$; that is, at $(63,31)$. This is a small-$k$ case. We take 32 small-$k$ steps down to $(31,31)=992$. The question asked about what happens up to when there are $<1000$ prisoners. Obviously the round of executions leading to 992 (half of one of our "steps") started above 1000, since at this point each round is killing 30ish prisoners. So we stop at 992, and the number of people executed is $4000-992=3008$.