Qiitaで自作の素因数分解プログラムを公開したら添削されて30倍速くなった件(2) - Qiita

前回のあらすじ 自作の素因数分解プログラムを Qiita で公開した。 プログラムに添削が入り，30倍以上速くなった。 なぜ速くなったのか，逆になぜ自作プログラムは遅かったのか考えた。 そのまま使うのもアレなので添削プログラムを改良して少しだけ速くした。 詳しくは下記の記事を参照されたい。 エラトステネスの篩（ふるい） 素数判定では片っ端から自然数で割って確認してみるのだが（試し割りという），除算は現代の最新プロセッサでも比較的コストのかかる計算であり，試し割りの回数はできるだけ抑制したい。 このため当初の自作プログラムでは，試し割りをする回数を抑えるために試し割りをする自然数の素数判定を行っていたのだが，素数判定ルーチンの中で試し割りをしていたので意味がなかった。というか逆に計算量が大幅に増えてしまっていた。親会社は経営合理化したつもりで，単に子会社に面倒を押し付けただけっていうアレよ。