ルートNまででOKな理由は数学的センスないと解らないから、N/2まででいいと思う。
NがN/2より大きい数で割れないことくらいは解るからw