エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件(6) - Qiita
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件(6) - Qiita
前回までのあらすじ 自作の素因数分解プログラムを Qiita で公開した。プログラムに添削が入り,30倍以... 前回までのあらすじ 自作の素因数分解プログラムを Qiita で公開した。プログラムに添削が入り,30倍以上速くなった。ちなみに教えて頂いた方法は「試し割り法」と呼ばれている。教えられた方法をそのまま使うのもアレなので,もっと速い方法を編み出せないか考えてみた。 現代のプロセッサでも割り算は比較的重いとされるので,与えられた自然数 $n$ に対してエラトステネスの篩(ふるい)と呼ばれる手法を用いて $\sqrt{n}$ 以下の素数を列挙し,それらの素数だけで試し割りをすれば除算回数は最小化され,格段の高速化が期待できるはずだ!しかし,エラトステネスの篩(ふるい)は大量にメモリを使用するせいか,意図したほど速くならなかった。 一方,試し割り法は $\sqrt{n}$ 以下の自然数すべてで割るのではなく,奇数だけ,あるいは2・3の倍数を除いた場合,2・3・5の倍数を除いた場合など除算回数を減ら