単純にふるいがけすると10億要素必要だからキツイ。
2 3の倍数を除いたとしても3億なのでキツイ。
9桁までの素数を配列に詰めて2分探索するのがいいと思う