Problem 3 - Project Euler
600851475143 の素因数のうち最大のものを求めよ。
大きすぎる数値
素数のリストが作れてしまえば簡単なんですが、昨日も書いたように数値が大きすぎてlong型になってしまいます。xrangeはlong型は扱えないみたい（int型に変換しようとするっぽい）なのです。python 3 ならとも思ったんですが、これもメモリエラー。
ちょっとズルしてみた
まず、600851475143という数字は奇数ですので、素因数は少なくとも3以上になります。そうすると、素因数で最も大きな数は600851475143の3乗根以下になるはずです。（追記）何を寝ぼけてたか知りませんが、3乗根ではなく3分の1が正解ですね。失礼しました。
n乗根を求めるにはmathモジュールのpow関数を使用します。
import math math.pow(600851475143, (1.0/3.0)) # 8438.3145557747084
これで素因数は8439より小さい事がわかりました。（追記）上にも書きましたが、これは間違いです。
素数のリストは素数のリストを生成する（エラトステネスの篩） - kk6のメモ帳*を利用して求めます。
p = Eratos(8439) p.search_prime() [i for i in p.prime if 600851475143 % i == 0] [71, 839, 1471, 6857] #600851475143 の素因数のうち最大のものは6857
