n〜√N くらいまでなら重ならない確率も結構高い

らしい。

勉強になるのぉ。

というか n 〜 sqrt(N) ぐらいだと重ならないってのは、面白いというか今後にいかせる話ですね！