エラトステネスの篩は指定された整数以下の全ての素数を発見するためのアルゴリズムで①探索リストに2からxまでの整数を昇順で入れる②探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす③上記の篩い落とし操作を探索リストの先頭…

試し割り法は素数を求める手法で、nが素数であるかどうかを調べる場合nよりも小さい数で割って割り切れるかどうか調べるシンプルなアルゴリズムです。効率化するポイントとして①√nまでの数を調べれば十分②小さい数の方が割れる確率が高いため小さい数から調…