エラトステネスの篩っていう有名なアルゴリズムがあるよ。
割算を使わないのでかなり速くなるはず。
メモリたくさん使うけど常駐するわけじゃないし…

# てか1000万って篩に使うメモリを意識して選んだのかと思ってた。