For what it's worth, the $\sqrt{N}$ approximation is accurate up to a constant factor; for $N = 2^{32}$, the actual threshold is $77\,164$, as this is the smallest value of $n$ such that \[ \prod_{k=1}^{n-1} (1 - k / N) < 1 / 2. \]