Q&A
素数の一覧を求める際に効率化を図ることは可能でしょうか？
自分が考えた方法として、例えば100万までの素数を求めたいとして、
それの三乗根は100じゃないですか。
逆に言うと、それを1でも超えたら、求めたい1000000を超えてしまうわけですよね。
なので、100までエラストステネスの篩で落として、
あとは残りの素数のコンビネーションを使えばはやいんじゃないかと考えたわけです。
平方根は1000ですが、100から1000までの整数が全てびっちり素数だとして、これらの数の二つの組み合わせをしていくだけなので、計算量は407252ですみます。
ふるい落としていく段階で、全てのリストを素数ごとに見渡していくよりも、ターゲットを絞って消していった方が効率がいいような気がするのですが、実際にこのやり方でやってみるとリストの検索で時間がかかるらしくてうまくいきませんでした。
このような考え方でなんとかして効率化をはかることはできないでしょうか？
宜しく御願いいたします。
回答1件
0
自己解決
質問が曖昧であった為自己解決にします
投稿2019/06/18 03:27
総合スコア107
下記のような回答は推奨されていません。
このような回答には修正を依頼しましょう。