Q&A
素数の一覧を求める際に効率化を図ることは可能でしょうか？
自分が考えた方法として、例えば100万までの素数を求めたいとして、
それの三乗根は100じゃないですか。
逆に言うと、それを1でも超えたら、求めたい1000000を超えてしまうわけですよね。
なので、100までエラストステネスの篩で落として、
あとは残りの素数のコンビネーションを使えばはやいんじゃないかと考えたわけです。
平方根は1000ですが、100から1000までの整数が全てびっちり素数だとして、これらの数の二つの組み合わせをしていくだけなので、計算量は407252ですみます。
ふるい落としていく段階で、全てのリストを素数ごとに見渡していくよりも、ターゲットを絞って消していった方が効率がいいような気がするのですが、実際にこのやり方でやってみるとリストの検索で時間がかかるらしくてうまくいきませんでした。
このような考え方でなんとかして効率化をはかることはできないでしょうか？
宜しく御願いいたします。
自己解決
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。