Project Euler 153(1)

この問題はメモリを多く使えば簡単のようですが、いつもやっているように300MBを目標にしてPythonでなるべく速くなるようにします。

ガウス整数の範囲で約数の和を求めるということなので、素因数分解ができれば約数は簡単に求められるでしょう。ガウス整数素因数分解の一意性から、整数の範囲で素因数分解して、それから素数素因数分解すればよいです。
そのためにまず素数素因数分解を求めておきましょう。単純に考えて、自然数を一つずつ素因数分解して、(a + bi)(a - bi)という形(a > b)になったら、(a, b)というタプルをリストに入れるということにしましょう。

これで7秒でした。問題は108なので話になりませんね。O(N1.5)のはずなので。
一つずつ計算してダメなときはまとめて計算ですね。逆にabを回して、a2 + b2 = nならn素因数分解は(a + bi)(a - bi)と考えます。

これだとO(N)になるはずです。これで25秒でした。遅いですね。しかもメモリを130MBも使っていました。このようにタプルをリストに入れると非常に多くのメモリを使います。

これで5秒でした。単にタプルをリストに入れるだけで遅いようです。
タプルはやめて、リストを2つ使いましょう。こうすればメモリ使用量も少なくなります。

これで7秒、90MBでした。単純に考えれば整数一つで4バイトなので80MBになりそうですが。
ダイエットしてみましょう。3より大きい素数は6の剰余が1か5です。さらに、分解できる素数は4の剰余が1なので、12の剰余が1か5になります。だからメモリ使用量は1/6にできます。

あと、abはどちらかが偶数でどちらかが奇数なので、回すbを半分にできます。また、bnがN以下になるように制限して、

これで50秒でした。このあとの処理を入れると1分は切れなさそうですね。