2010-07-14から1日間の記事一覧

Haskellでエラトステネスの篩

優先順位つきキューを用いたエラトステネスの篩の変形がある。 優先順位つきキューの削除と挿入のコストをO(log n)とすると、エラトステネス全体のオーダーはO(n log^2 n)である。追記:以下は整数値オーバーフローのため値がおかしい。かつ、修正すると低速…