先ほどアトキンの篩を論文(http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf)通りに実装したのですが、メモリ消費量が大きく、n=10^9程度になるとメモリ不足となってしまいます。
そして、論文では区間篩を用いることでメモリ消費のオーダーをO(sqrt(n))程度に落とせる記載がありました。
しかし、区間の取り方などをいまいち読み解けず実装できそうにありません。
どなたか知識をお持ちの方がいらっしゃいましたら、必要な手順について教えていただけないでしょうか。
一応、日本語で簡潔にまとめていらっしゃる方もいるのですが(http://d.hatena.ne.jp/uwitenpen/20111203)、私ではうまく読み解けませんでしたので、詳細にご教授願えれば幸いです。
あなたの回答
tips
プレビュー