読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 179 / 連続する正の約数

n と n + 1 の正の約数の個数が等しい 1 < n < 10^7 の整数は何個あるか。

Problem 179 - Project Euler

brute force

約数の個数を扱う問題は前にもやりました。DivisorSigma[0, #] で約数の0乗の和を求めて比較します。この方法だと96秒。


並列化

第146問でやったのと同じように並列化してみます。

variee.hatenadiary.com

まずは第146問と近い形でやってみましたが,一向に答えが帰ってこず,abort せざるを得ませんでした。アクティビティモニタによるとCPU使用率も20%ほどしかなく,これは並列化むきの処理法ではなかったようです。


ParallelSum を使うと3.7秒。コードも短くていいですね。CPU使用率は90%以上いきました。


さらに最適化。オンラインヘルプに

計算をできるだけ少ない部分に分割することで並列オーバーヘッドを小さくするには Method -> "CoarsestGrained" をつけるとよい

とあったのでやってみました。結果は2.2秒。最初と比べると42倍の速さです。