In order for the remainder to be $r$ (where $0 \le r < \sqrt{N}$), we need $N-r$ to have an odd divisor $m$ with
$r < m \le \sqrt{N}$.  It can't happen if $N-r$ is prime; on the other hand, if $N-r$ is a product of many small primes there should be lots of such $m$.