half the prime number

アリストテレスの篩を用いて素数を全列挙すると解を求めることができます。計算量は$\mathcal{O}(NloglogN)$で十分高速です。