Project Euler 3 高速化とは？

1877 ワード
ProjectEuler Python Python テキストリンク

13195 の素因数は 5, 7, 13, 29 である.

600851475143 の素因数のうち最大のものを求めよ.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%203

思いつくまま解いてみた。

target = 600851475143
i = 1
while target != 1:
  i += 2
  while not target % i:
    target /= i
print i

これは600851475143が合成数であることを前提とした回答である。合成数であるがゆえに、while文もそんなに繰り返されるわけでない。よってこのコードでも問題はない。
ただ、600851475143が素数であった場合、このコードには問題が生じることとなる。600851475143/2 約3兆回程剰余を計算することとなる。

つまり、次のようなシュチュエーションが生じることとなる。

サービス提供においては、早くて問題になることはなく、遅いと問題になりがちである。このような観点からすると、仮に素数であったとしてもリスクヘッジの観点からその遅さを回避できる次のようなコードが好ましいのかもしれない。
次のコードではエラトステネスの篩もろもろでtargetの平方根まで素数のリストを作成し、そのリストを基に素因数分解を試みている。すべての素数で剰余計算を行わない点、targetの平方根までしか計算を行わない点で、安定した処理速度がでるんじゃないかと思われる。（targetの平方根までしか計算を行わないのは上のコードでもできるけど。）

import mymath
import math
target = 600851475143
pri = mymath.get_primes(int(math.sqrt(target)))
max_p = 1
for p in pri['list']:
    while not target % p:
        target /= p
        max_p = p
if target != 1:
    print target
else:
    print max_p

なお、mymathはこちら。
http://www.sato-pat.co.jp/